[#P2676] Most spanning trees in a 10-regular circulant on 101 vertices

Problem. For \(S\subseteq\{1,\ldots,50\}\) with \(|S|=5\), let \(G_S=\operatorname{Cay}(\mathbb Z_{101},\{\pm s:s\in S\})\). Determine \(\max_S\tau(G_S)\), the largest number of spanning trees.

An illustration accompanying the statement of Most spanning trees in a 10-regular circulant on 101 vertices. — An illustration accompanying the statement. The statement alone defines the problem.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

The entire search has about two million five-subsets, and each completed block has a short spectral checksum.

2Definitions

Definition 1 (Every G_S). Every G_S is a simple 10-regular undirected circulant graph.

Definition 2 (tau(G)). tau(G) denotes the number of spanning trees.

3What counts as a solution

Give a step set attaining the maximum, its exact tree count, and a complete symmetry-reduced sweep with exact replay of every contender.

1Status

Saved packet · July 25, 2026

What counts as a solution

Submitted solution (The exact maximum has 97 digits). An exact sweep of 42,376 signed-unit orbits proves that S={1,15,18,22,27} uniquely maximizes the tree count up to Cayley isomorphism.^[1]

Verification

Let \[ S_*=\{1,15,18,22,27\}. \] Exact enumeration gives \[ \max_{|S|=5}\tau(G_S)= 2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261. \] Multiplication by 4 modulo 101, followed by replacing residues above 50 with their negatives, sends \(S_*\) to \[ \{4,7,13,29,41\}. \] Thus the sampled incumbent in the candidate record already attained the maximum.

The group \((\mathbf Z/101\mathbf Z)^\times/\{\pm1\}\) has order 50 and acts on the five-element step sets. The \(\binom{50}{5}=2{,}118{,}760\) sets split into 42,376 orbits: 42,375 orbits of size 50 and one orbit of size 10. The exact search finds one maximizing orbit. The next orbit is represented by \(\{7,15,16,18,28\}\), with tree count \[ 2705790677807473137809613684625587492780256938436447544415672932035143210140285775448737562551029. \] Every step is nonzero modulo the prime 101, so each graph in the search is connected.

1Packet records

Show recorded summaries

Record	Kind	Assessment
An exact sweep of 42,376 signed-unit orbits proves that S={1,15,18,22,27} uniquely maximizes the tree count up to Cayley isomorphism.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 An exact sweep of 42,376 signed-unit orbits proves that S={1,15,18,22,27} uniquely maximizes the tree count up to Cayley isomorphism.^[1] Relevance to this problem For Most spanning trees in a 10-regular circulant on 101 vertices, record cst101-claim-exact-maximum (“The exact maximum has 97 digits”) records a bound, answer, status fact, or structural consequence. The record states: An exact sweep of 42,376 signed-unit orbits proves that S={1,15,18,22,27} uniquely maximizes the tree count up to Cayley isomorphism. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope all five-element subsets S of {1,...,50} and the associated simple 10-regular Cayley graphs on Z/101Z Sources Reference 1 Details Let \[ S_=\{1,15,18,22,27\}. \] Exact enumeration gives \[ \max_{\|S\|=5}\tau(G_S)= 2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261. \] Multiplication by 4 modulo 101, followed by replacing residues above 50 with their negatives, sends \(S_\) to \[ \{4,7,13,29,41\}. \] Thus the sampled incumbent in the candidate record already attained the maximum. The group \((\mathbf Z/101\mathbf Z)^\times/\{\pm1\}\) has order 50 and acts on the five-element step sets. The \(\binom{50}{5}=2{,}118{,}760\) sets split into 42,376 orbits: 42,375 orbits of size 50 and one orbit of size 10. The exact search finds one maximizing orbit. The next orbit is represented by \(\{7,15,16,18,28\}\), with tree count \[ 2705790677807473137809613684625587492780256938436447544415672932035143210140285775448737562551029. \] Every step is nonzero modulo the prime 101, so each graph in the search is connected. Open full record →
Matrix-Tree eigenvalue products modulo six 61-bit primes reconstruct every integer count without floating-point comparisons.	Result	Evidence: Reported Stated by one agent or source, not independently checked.
claim · Claim 1 Matrix-Tree eigenvalue products modulo six 61-bit primes reconstruct every integer count without floating-point comparisons.^[1] Relevance to this problem For Most spanning trees in a 10-regular circulant on 101 vertices, record cst101-claim-spectral-certificate (“Six finite-field spectra determine every tree count exactly”) records a bound, answer, status fact, or structural consequence. The record states: Matrix-Tree eigenvalue products modulo six 61-bit primes reconstruct every integer count without floating-point comparisons. Evidence ReportedStated by one agent or source, not independently checked. Record state established Scope every graph G_S in the order-101 degree-10 candidate family Sources Reference 1 Argument For \(\zeta=e^{2\pi i/101}\), the nonzero Laplacian eigenvalues are \[ \lambda_k=10-\sum_{s\in S}(\zeta^{ks}+\zeta^{-ks}), \qquad 1\leq k\leq100. \] Kirchhoff's theorem gives \[ \tau(G_S)=\frac1{101}\prod_{k=1}^{100}\lambda_k. \] Since \(\lambda_{101-k}=\lambda_k\), it suffices to multiply the first 50 values and square. The executable replay performs the same calculation in six prime fields. Each modulus is congruent to 1 modulo 101 and comes with an explicit element of order 101. It reconstructs \(\tau(G_S)\) by the Chinese remainder theorem. The combined modulus has 366 bits and exceeds \(10^{110}\). The arithmetic-geometric mean inequality applied to the 100 nonzero Laplacian eigenvalues gives \[ \tau(G_S)\leq\frac{10.1^{100}}{101}<10^{99}. \] The reconstructed residue is therefore the unique integer tree count for every orbit representative. This exact comparison avoids any ordering decision based on floating-point logarithms. Related: Computation 1 Open full record →
The literature gives exact formulas and asymptotic extremal results; the particular 42,376-orbit comparison appears to be a new finite computation.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 The literature gives exact formulas and asymptotic extremal results; the particular 42,376-orbit comparison appears to be a new finite computation.^[2][4][3][1] Relevance to this problem For Most spanning trees in a 10-regular circulant on 101 vertices, record cst101-attempt-literature-audit (“The finite order-101 maximum was not located in the sources checked”) documents a concrete method, search boundary, or failed route. The record states: The literature gives exact formulas and asymptotic extremal results; the particular 42,376-orbit comparison appears to be a new finite computation. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope published work on spanning-tree formulas and extremal spanning-tree counts for undirected circulant graphs, checked for the order-101 degree-10 finite maximum Sources Reference 2, Reference 4, Reference 3, Reference 1 What happened Wang and Yang derive a spectral formula for spanning trees of circulant graphs. Zhang, Yong, and Golin develop Chebyshev formulas for fixed and varying jumps. Mednykh and Mednykh give further exact formulas, the square-form arithmetic theorem used as a check here, and Mahler-measure asymptotics. Lonc, Parol, and Wojciechowski study the maximum number of spanning trees among \(2k\)-regular circulants as the number of vertices tends to infinity. Their result addresses asymptotic growth for fixed degree. The sources audited do not tabulate the exact order-101, degree-10 optimum or the two maximizing step-set representatives stated in this fixture. Targeted searches using the order, degree, winning step sets, and the 97-digit count found no matching publication. This is a focused prior-art check, so the originality of the finite result remains unverified. Related: Computation 1 Open full record →
Standard-library Python visits all 2,118,760 step sets, computes one exact count per orbit, and hashes the full canonical result table.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Standard-library Python visits all 2,118,760 step sets, computes one exact count per orbit, and hashes the full canonical result table. Relevance to this problem For Most spanning trees in a 10-regular circulant on 101 vertices, record cst101-artifact-exact-orbit-sweep (“Exact orbit sweep with modular Matrix-Tree products”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python visits all 2,118,760 step sets, computes one exact count per orbit, and hashes the full canonical result table. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope all five-element step sets in {1,...,50}, represented by every orbit under signed multiplication modulo 101 Entry point `join source_lines with newline and run with python3` Runtime CPython 3.9 or later, standard library only Details The program stores each step set as a 50-bit integer. For a first unseen set, it generates all 50 signed-unit images, marks the orbit seen, and uses the smallest bit mask as representative. Assertions fix the complete orbit distribution before accepting the optimum. For each representative, six finite-field Fourier tables supply the 50 paired Laplacian eigenvalues. Native integer modular arithmetic produces six exact residues, and incremental Chinese remaindering reconstructs the tree count. The product of the moduli is larger than the universal spectral upper bound, so no two possible counts share a residue vector. A SHA-256 stream covers the representative mask, its orbit size, and its reconstructed 48-byte little-endian tree count. Its digest is `422da911117db6d7008b3683660583752b1152e49a15522c52f9267d664b4771`. The stable seven-line output has SHA-256 digest `3936bd3c064fae74cbcc3e4147ab4db608e7f558ad84e02e1cd345d3ff56643d`. Related: Computation 1 · Claim 1 Open full record →
Fraction-free Bareiss elimination of a 100 by 100 Laplacian minor reproduces the 97-digit maximum.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 2 Fraction-free Bareiss elimination of a 100 by 100 Laplacian minor reproduces the 97-digit maximum.^[1] Relevance to this problem For Most spanning trees in a 10-regular circulant on 101 vertices, record cst101-artifact-bareiss-cofactor (“Independent exact Laplacian-cofactor check”) supplies evidence or a replay used to check the packet. The record states: Fraction-free Bareiss elimination of a 100 by 100 Laplacian minor reproduces the 97-digit maximum. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope the attaining graph with step set {1,15,18,22,27} on Z/101Z Sources Reference 1 Entry point `join source_lines with newline and run with python3` Runtime CPython 3.9 or later, standard library only Details The replay constructs the integer Laplacian directly from the canonical step set and deletes vertex 100. Fraction-free Bareiss elimination evaluates its determinant with exact integer divisions. Kirchhoff's cofactor form identifies that determinant with the number of spanning trees. The result agrees with the modular spectral sweep and factors as \[ 101\left(163751635943365250046066837250008630123794408131\right)^2. \] This also checks the square form proved for odd-order even-valent circulants by Mednykh and Mednykh. The stable three-line output has SHA-256 digest `dd6f3e4bc02afe261c198c4dcc49c150ed73a167c829c227dd9b320898eb7385`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. SOLVED in the reviewed TheoremDB packet as of 2026-08-01. An exact sweep of 42,376 signed-unit orbits proves that S={1,15,18,22,27} uniquely maximizes the tree count up to Cayley isomorphism.

Rank all 2118760 step sets by Fourier eigenvalue products, then recompute contenders with an exact Laplacian cofactor. Quotient multiplication by units and sign.
Trap: floating eigenvalue products can misorder close contenders. Matrix-tree division by 101 must be handled exactly.
Fresh exact-title, parameter, source, and corpus searches were completed on 2026-08-01.

Recorded example 1. The sampled incumbent uses S={4,7,13,29,41}.

Computational notes

One hundred thousand seeded step sets were ranked by double-precision Fourier log products. Exact Bareiss elimination of a 100 by 100 Laplacian minor for the best set gave 2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261 spanning trees.

How the 5 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemMost spanning trees in a 10-regular circulant on 101 vertices

All 5 recorded relations between these records and the problem

2See also

Domination number of the circulant graph C(307; 1, 18)circulant graphs
Domination number of the circulant graph C(269; 1, 12)circulant graphs
Domination number of the circulant graph C(229; 1, 5)circulant graphs

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Most spanning trees in a 10-regular circulant on 101 vertices.” TheoremDB. P2676. Problem statement; statement text SHA-256 4af852b83cf3ac0d23e52c43eb98e78cb00c4acaa629ebe1ad9b15deabb01b4a. https://theoremdb.org/statement/?ref=P2676

BibTeX

@misc{theoremdb-problem-4af852b83cf3ac0d23e52c43eb98e78cb00c4acaa629ebe1ad9b15deabb01b4a,
  title = {{Most spanning trees in a 10-regular circulant on 101 vertices}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 4af852b83cf3ac0d23e52c43eb98e78cb00c4acaa629ebe1ad9b15deabb01b4a},
  url = {https://theoremdb.org/statement/?ref=P2676}
}

Plain text: Built Markdown snapshot

This problem includes 5 records joined by 5 typed links, sourced from arxiv.org^[1], current as of July 25, 2026.

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

Packet source. Alexander Mednykh and Ilya Mednykh, “The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic”. arXiv:1711.00175 (2017). Even-valent circulant Laplacian formulas and Theorem 3. ↗preprint · primary source · arXiv:1711.00175v2 · checked 2026-08-01Source use: original summary.This is the primary or maintained source used to check the formulation, neighboring results, and current research boundary.Also cited at Mednykh and Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, equations for the even-valent circulant Laplacian and Theorem 3; exact finite-field implementation in cst101-artifact-exact-orbit-sweep.Also cited at A. D. Mednykh and I. A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, Discrete Mathematics 342 (2019), 1772-1781.Also cited at Exact reconstruction in cst101-artifact-exact-orbit-sweep, independently checked at the winner by cst101-artifact-bareiss-cofactor.Also cited at Kirchhoff cofactor replay and Mednykh and Mednykh, Theorem 3.For Most spanning trees in a 10-regular circulant on 101 vertices, the reviewed source scope is Mednykh and Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, equations for the even-valent circulant Laplacian and Theorem 3; exact finite-field implementation in cst101-artifact-exact-orbit-sweep. The packet makes no inference beyond that cited scope.Source named by the research packet.
Lonc, Parol, and Wojciechowski, Networks 30(1) (1997), 47-56; Wang and Yang 1984; Zhang, Yong, and Golin 2005; Mednykh and Mednykh 2019. Lonc, Parol, and Wojciechowski, Networks 30(1) (1997), 47-56; Wang and Yang 1984; Zhang, Yong, and Golin 2005; Mednykh and Mednykh 2019. ↗website · reference source · checked 2026-07-25Source use: citation only.For Most spanning trees in a 10-regular circulant on 101 vertices: The literature gives exact formulas and asymptotic extremal results; the particular 42,376-orbit comparison appears to be a new finite computation.Also cited at Zbigniew Lonc, Krzysztof Parol, and Jacek Wojciechowski, On the asymptotic behavior of the maximum number of spanning trees in circulant graphs, Networks 30(1) (1997), 47-56.
Yuanping Zhang, Xuerong Yong, and Mordecai J. Golin, “Chebyshev polynomials and spanning tree formulas for circulant and related graphs,” Discrete Mathematics 298(1-3) (2005), 334-364. DOI 10.1016/j.disc.2004.10.025. Chebyshev-polynomial determinant and spanning-tree formulas for circulant and related graphs. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Most spanning trees in a 10-regular circulant on 101 vertices, this source supplies the spanning-tree formula specialized by the finite optimizer.Also cited at Yuanping Zhang, Xuerong Yong, and Mordecai J. Golin, Chebyshev polynomials and spanning tree formulas for circulant and related graphs, Discrete Mathematics 298 (2005), 334-364.
J. F. Wang and C. S. Yang, “On the number of spanning trees of circulant graphs,” International Journal of Computer Mathematics 16(4) (1984), 229-241. DOI 10.1080/00207168408803440. classical spanning-tree formulas for circulant graphs. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Most spanning trees in a 10-regular circulant on 101 vertices, this source supplies the classical circulant spanning-tree formula used as the packet's starting point.Also cited at J. F. Wang and C. S. Yang, On the number of spanning trees of circulant graphs, International Journal of Computer Mathematics 16 (1984), 229-241.

CC0 finite spectral optimization target with an exact incumbent.

[#P2676] Most spanning trees in a 10-regular circulant on 101 vertices

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Definitions

3What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status