pith. sign in

arxiv: 1907.02635 · v1 · pith:CTQ5CTN2new · submitted 2019-07-04 · 🧮 math.CO

The number of rooted forests in circulant graphs

L.A. Grunwald , I.A. Mednykh This is my paper

Pith reviewed 2026-05-25 09:44 UTC · model grok-4.3

classification 🧮 math.CO
keywords circulant graphsrooted spanning forestsChebyshev polynomialsMahler measureLaplacian eigenvaluesasymptotic formulasinteger sequences
0
0 comments X

The pith

The number of rooted spanning forests in circulant graphs equals p times the square of an integer sequence derived from Chebyshev polynomials.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops explicit formulas using Chebyshev polynomials for the number of rooted spanning forests in two types of circulant graphs. It establishes that these numbers always take the form p a(n)^2, where a(n) is an integer sequence and p depends on the parity of n. The work also provides an asymptotic formula based on the Mahler measure of a Laurent polynomial associated with the graph. A reader would care because the results convert a hard counting problem into computable algebraic expressions and growth rates.

Core claim

We develop a new method to produce explicit formulas for the number f_G(n) of rooted spanning forests in the circulant graphs G=C_n(s_1,s_2,…,s_k) and G=C_{2n}(s_1,s_2,…,s_k,n). These formulas are expressed through Chebyshev polynomials. We prove that in both cases the number of rooted spanning forests can be represented in the form f_G(n)=p a(n)^2, where a(n) is an integer sequence and p is a prescribed natural number depending on the parity of n. Finally, we find an asymptotic formula for f_G(n) through the Mahler measure of the associated Laurent polynomial P(z)=2k+1−∑(z^{s_i}+z^{-s_i}).

What carries the argument

Chebyshev polynomials obtained from the roots-of-unity eigenvalues of the circulant graph Laplacian, which yield the squared form for the forest count.

If this is right

  • The count f_G(n) is always an integer multiple of a square for these graphs.
  • The growth rate of f_G(n) is determined by the Mahler measure of P(z).
  • Explicit formulas apply uniformly to both the listed families of circulant graphs.
  • Integer sequence a(n) satisfies recurrence relations from Chebyshev polynomial properties.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The squared structure may reflect a natural involution on the set of forests.
  • Connections to Mahler measures suggest possible links to entropy calculations in dynamical systems on circles.
  • Similar eigenvalue techniques could apply to counting problems in other symmetric graphs.

Load-bearing premise

The eigenvalues and eigenvectors of the Laplacian admit an explicit closed-form description via roots of unity that directly produces Chebyshev polynomials without additional case-by-case adjustments.

What would settle it

For a small circulant graph such as C_4(1), compute the number of rooted spanning forests by the matrix-tree theorem and check whether it equals p a(4)^2 for the p and a(n) predicted by the Chebyshev formula.

read the original abstract

In this paper, we develop a new method to produce explicit formulas for the number $f_{G}(n)$ of rooted spanning forests in the circulant graphs $ G=C_{n}(s_1,s_2,\ldots,s_k)$ and $ G=C_{2n}(s_1,s_2,\ldots,s_k,n).$ These formulas are expressed through Chebyshev polynomials. We prove that in both cases the number of rooted spanning forests can be represented in the form $f_{G}(n)=p\,a(n)^2,$ where $a(n)$ is an integer sequence and $p$ is a prescribed natural number depending on the parity of $n$. Finally, we find an asymptotic formula for $f_{G}(n)$ through the Mahler measure of the associated Laurent polynomial $P(z)=2k+1-\sum\limits_{i=1}^k(z^{s_i}+z^{-s_i}).$

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript develops a spectral method to derive explicit formulas, expressed via Chebyshev polynomials, for the number f_G(n) of rooted spanning forests in the circulant graphs G = C_n(s_1,...,s_k) and G = C_{2n}(s_1,...,s_k,n). It proves that in both cases f_G(n) = p a(n)^2 for an integer sequence a(n) and a natural number p depending on the parity of n. It also derives an asymptotic formula for f_G(n) in terms of the Mahler measure of the Laurent polynomial P(z) = 2k + 1 - sum_{i=1}^k (z^{s_i} + z^{-s_i}).

Significance. If the derivations are correct, the results supply closed-form expressions and asymptotics for spanning-forest enumeration in two families of vertex-transitive graphs, which may be of interest in algebraic combinatorics. The explicit representation as p a(n)^2 and the link to Mahler measure constitute concrete, falsifiable outputs.

major comments (1)
  1. [Abstract] Abstract: the claim that the same Laurent polynomial P(z) = 2k + 1 - sum (z^{s_i} + z^{-s_i}) governs both families is not supported for the second family. For C_{2n}(s_1,...,s_k,n) the Laplacian eigenvalues contain an extra -2(-1)^j term arising from the diameter edges; this term is absent from the stated P(z) and cannot be absorbed by evaluating P on 2n-th roots of unity. Consequently the product formula for f_G(n) and the Mahler-measure asymptotic do not hold uniformly for both families as asserted.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for identifying the imprecision in the abstract. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that the same Laurent polynomial P(z) = 2k + 1 - sum (z^{s_i} + z^{-s_i}) governs both families is not supported for the second family. For C_{2n}(s_1,...,s_k,n) the Laplacian eigenvalues contain an extra -2(-1)^j term arising from the diameter edges; this term is absent from the stated P(z) and cannot be absorbed by evaluating P on 2n-th roots of unity. Consequently the product formula for f_G(n) and the Mahler-measure asymptotic do not hold uniformly for both families as asserted.

    Authors: We agree with the referee that the abstract overstates the uniformity of the Laurent polynomial P(z) across both families. For the graph C_{2n}(s_1,...,s_k,n), the eigenvalues of the Laplacian indeed include the additional contribution -2(-1)^j from the diameter edges, which is not present in the stated P(z) and cannot be absorbed simply by substitution at 2n-th roots of unity. The derivations in the body of the paper treat the two families separately, with the product formula for the number of rooted forests obtained by direct computation of the eigenvalues in each case. We will revise the abstract to distinguish the associated Laurent polynomials for the two families and to state the product formulas and asymptotic results with the appropriate precision for each case. The explicit Chebyshev expressions and the representation f_G(n) = p a(n)^2 remain valid as derived case by case. revision: yes

Circularity Check

0 steps flagged

No circularity: standard spectral derivation from Laplacian eigenvalues to product formula and Mahler asymptotic

full rationale

The paper states that the number of rooted spanning forests equals a product over the nonzero Laplacian eigenvalues of the circulant graph, which for these graphs are given explicitly by evaluating the stated Laurent polynomial P at roots of unity; the Chebyshev expressions and the p a(n)^2 form are obtained by direct algebraic manipulation of that product, while the asymptotic follows from the definition of the Mahler measure applied to the same P. No step reduces a claimed prediction to a fitted parameter by construction, invokes a self-citation as the sole justification for a uniqueness or ansatz claim, or renames an input quantity. The derivation therefore remains self-contained against the external, independently verifiable spectral formula for circulant Laplacians.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard facts from algebraic graph theory (eigenvalues of circulant matrices) and properties of Chebyshev polynomials; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math The Laplacian matrix of a circulant graph is diagonalized by the Fourier basis of roots of unity.
    Invoked implicitly to obtain the explicit spectrum needed for the forest count via the matrix-tree theorem generalization.
  • standard math Chebyshev polynomials satisfy the recurrence and generating-function identities used to sum the resulting products over eigenvalues.
    Standard background invoked to convert the product formula into closed form.

pith-pipeline@v0.9.0 · 5689 in / 1392 out tokens · 36225 ms · 2026-05-25T09:44:06.205072+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 4 internal anchors

  1. [1]

    Apostol, Introduction to Analytic Number Theory, Springer -Verlag, New York, 1976

    T.M. Apostol, Introduction to Analytic Number Theory, Springer -Verlag, New York, 1976

    work page 1976

  2. [2]

    T. L. Austin, The enumeration of point labelled chromatic graphs a nd trees, Canad. J. Math. 12 (1960) 535–545

    work page 1960

  3. [3]

    F. T. Boesch, H. Prodinger, Spanning tree formulas and Chebys hev polynomials, Graphs and Combinatorics 2(1) (1986) 191–200

    work page 1986

  4. [4]

    F. T. Boesch and Z. R. Bogdanowicz, The number of spanning tre ss in a prism, Internat. J. Comput. Math. 21 (1987) 229–243

    work page 1987

  5. [5]

    Calan, A combinatorial derivation of the number of labeled fore sts, Journal of Integer Sequences, 6(4) (2003), Art

    D. Calan, A combinatorial derivation of the number of labeled fore sts, Journal of Integer Sequences, 6(4) (2003), Art. 03.4.7, 1–3

    work page 2003

  6. [6]

    Cayley, A theorem on trees, Quart

    A. Cayley, A theorem on trees, Quart. J. Pure Appl. Math. 23 (1 889) 376–378

    work page

  7. [7]

    Chebotarev, E

    P. Chebotarev, E. Shamis, Matrix forest theorems, Preprint, 2006, arXiv:math/0602575 [math.CO] 25 Feb 2006

    work page arXiv 2006

  8. [8]

    P. J. Davis, Circulant Matrices, AMS Chelsea Publishing, 1994

    work page 1994

  9. [9]

    Everest, T

    G. Everest, T. Ward, Heights of polynomials and entropy in algebraic dynamics . (Springer Science & Business Media, 2013)

    work page 2013

  10. [10]

    Y. Jin, C. Lin, Enumeration for spanning forests of complete bip artite graphs, Ars Combinatoria, 70 (2004), 135–138

    work page 2004

  11. [11]

    A. J. Guttmann, M. D. Rogers, Spanning tree generating func tions and Mahler mea- sures. Journal of Physics A: Mathematical and Theoretical, 45(4 9), (2012), 494001. arXiv:1207.2815v2 [math-ph] 26 Aug 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  12. [12]

    A. J. W. Hilton, Spanning trees and Fibonacci and Lucas number s, Fibonacci Q. 12 (1974), 259–262

    work page 1974

  13. [13]

    P. W. Kasteleyn, Graph theory and crystal physics, in Graph T heory and Theoretical Physics, Academic Press, London 1967

    work page 1967

  14. [14]

    Kel’mans, V.M

    A.K. Kel’mans, V.M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, J. Combin. Theory, Ser. B 16 (1974 ) 197–214

    work page 1974

  15. [15]

    Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird, Ann

    G. Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Unter- suchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird, Ann. Phys. Chem., 72 (1847), 497–508

    work page

  16. [16]

    Counting rooted forests in a network

    O. Knill, Counting rooted forests in a network, Preprint, 2013, arXiv:1307.3810 [math.SP] 18 Jul 2013. 12

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  17. [17]

    Y. S. Kwon, A. D. Mednykh, I. A. Mednykh, On Jacobian group a nd complexity of the generalized Petersen graph GP (n, k) through Chebyshev polynomials, Linear Algebra and its Applications 529 (2017), 355–373

    work page 2017

  18. [18]

    D. H. Lehmer, Factorization of certain cyclotomic functions, A nn. of Math.(2) 34 (1933), 461–479

    work page 1933

  19. [19]

    C. J. Liu, Y. Chow, Enumeration of forests in a graph, Proc. of the American Math. Soc., 83 (1981), 659–662

    work page 1981

  20. [20]

    Lorenzini, Smith normal form and Laplacians, J

    D. Lorenzini, Smith normal form and Laplacians, J. Combin. Theo ry Ser. B., 98(6) (2008), 1271–1300

    work page 2008

  21. [21]

    Louis, Asymptotics for the Number of Spanning Trees in Circu lant Graphs and Degenerating d-Dimensional Discrete Tori, Annals of Combinatorics 19(3) (2015) 5 13– 543

    J. Louis, Asymptotics for the Number of Spanning Trees in Circu lant Graphs and Degenerating d-Dimensional Discrete Tori, Annals of Combinatorics 19(3) (2015) 5 13– 543

    work page 2015

  22. [22]

    Mahler, On some inequalities for polynomials in several variables , J

    K. Mahler, On some inequalities for polynomials in several variables , J. London Math. Soc. 37 (1962) 341–344

    work page 1962

  23. [23]

    I. A. Mednykh, On Jacobian group and complexity of I-graph I(n, k, l) through Chebyshev polynomials, Arc Math. Contemp. , 15(2) (2018), 467–485

    work page 2018

  24. [24]

    A. D. Mednykh, I. A. Mednykh, The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic, Discrete Math., 342 (2019), 1772–1781

    work page 2019

  25. [25]

    J. C. Mason, D. C. Handscomb, Chebyshev Polynomials. Taylor & Francis (2002), 360 pp

    work page 2002

  26. [26]

    Schwenk, Computing the characteristic polynomial of a grap h

    A. Schwenk, Computing the characteristic polynomial of a grap h. In: Graphs and Combinatorics, Lecture Notes in Mathematics 406, pp. 153–172. B erlin-Heidelberg- New York: Springer-Verlag 1974

    work page 1974

  27. [27]

    Sedl´ acˇ ek, On the spanning trees of finite graphs, ˇCas

    J. Sedl´ acˇ ek, On the spanning trees of finite graphs, ˇCas. Pˇ estov´ an ´ ı Mat., 94 (1969), 217–221

    work page 1969

  28. [28]

    Sedl´ acˇ ek, On the skeletons of a graph or digraph

    J. Sedl´ acˇ ek, On the skeletons of a graph or digraph. In: Com binatorial Structures and their Applications, edited by R. Guy, M. Hanani, N. Saver, J. Sch onheim, pp. 387–391. New York: Gordon and Breach 1970

    work page 1970

  29. [29]

    Shrock and F.Y

    R. Shrock and F.Y. Wu, Spanning trees on graphs and lattices in d-dimensions J. Phys. A 33 (2000) 3881–3902

    work page 2000

  30. [30]

    D. S. Silver, S. G. Williams, Spanning Trees and Mahler Measure, Pr eprint, 2017, arXiv: 1701.06097v1 [math.CO] 21 Jan 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  31. [31]

    On conformal moduli of polygonal quadrilaterals

    Ch. Smyth, The Mahler measure of algebraic numbers: a survey , arXiv: math/0701387v3 [math.NT] 28 Jan 2008, 13

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  32. [32]

    W. Sun, S. Wang and J. Zhang, Counting spanning trees in prism a nd anti-prism graphs, J. Appl. Anal. Comput. 6 (2016) 65–75

    work page 2016

  33. [33]

    Tak´ acs, On the number of distinct forests, SIAM J

    L. Tak´ acs, On the number of distinct forests, SIAM J. Disc. Math. , 3(4) (1990), 574–581

    work page 1990

  34. [34]

    Templerley, M

    H. Templerley, M. Fisher, The dimer problem in statistical mechan ics an exact result. Phil. Mag. 6(1961), 1061–1063

    work page 1961

  35. [35]

    Weinberg, Number of trees in graph, Proc

    L. Weinberg, Number of trees in graph, Proc. IRE, 46 (1958), 1954–1955

    work page 1958

  36. [36]

    F. Y. Wu, Number of spanning trees on a lattice, J. Phys. A: Mat h. Gen. 10, (1977), L113–115

    work page 1977

  37. [37]

    282(1) (2004) 69–79

    Chen Xiebin, Qiuying Lin, Fuji Zhang, The number of spanning tre es in odd valent circulant graphs, Discrete Math. 282(1) (2004) 69–79

    work page 2004

  38. [38]

    Zhang Yuanping, Yong Xuerong, M. J. Golin, The number of span ning trees in cir- culant graphs, Discrete. Math. 223(1) (2000) 337–350

    work page 2000

  39. [39]

    Zhang Yuanping, Xuerong Yong, M. J. Golin, Chebyshev polynom ials and spanning tree formulas for circulant and related graphs, Discrete Math. 29 8(1) (2005) 334–364. 14

    work page 2005