Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Over a commutative Q-algebra, CYC⁡(A) has generating function ∑k≥1φ(k)klog⁡11−A(xk)

Statement

Let A be a combinatorial class with no size-zero objects, and write

A(x)=∑n≥1anxn.

Over a commutative Q-algebra,

OGF⁡(CYC⁡(A))=∑k≥1φ(k)klog⁡11−A(xk).

Facts & Assumptions

Given: A combinatorial class A with no size-zero objects and ordinary generating function A(x).

[L1]

Cauchy-Frobenius orbit counting: for a finite group action, ∣G∣ ∣X/G∣=∑g∈G∣Xg∣ (Cauchy-Frobenius orbit counting: ∣G∣ ∣X/G∣=∑g∈G∣Xg∣ for a finite group action).

[L2]

If d=gcd⁡(m,r), then an m-tuple fixed by rotation by r places is equivalently a repetition of one block of length d (A tuple fixed by a cyclic rotation is determined by a shorter periodic block).

[L3]

For k≥1, Euler's totient φ(k) is the number of unit classes in Z/k, and [s]k is a unit exactly when gcd⁡(s,k)=1 (The unit group (Z/n)× and Euler's totient φ(n)=∣(Z/n)×∣ for n≥1, For n≥1, [a]n is a unit if and only if gcd⁡(a,n)=1).

[L4]

The formal logarithm is log⁡(1+u)=∑j≥1(−1)j−1uj/j (Formal exponential, logarithm, and binomial powers over a commutative Q-algebra).

Proof

technique · direct
1.1L1

For each m≥1, let Cm be the class of cycles of length m. Since every object of A has positive size, an m-tuple of total size n can use only entries of size at most n, so every size layer of Am is finite. Applying [L1] degree by degree to the cyclic action of Cm therefore gives OGF⁡(Cm)=(1/m)∑r=0m−1Fm,r(x), where Fm,r(x) is the generating function of the m-tuples fixed by rotation by r places.

1.2L2

Put d:=gcd⁡(m,r) and k:=m/d. By [L2], a tuple fixed by rotation by r is obtained by repeating one block of length d. Each entry in that block is counted k times in the full cycle, so the generating function of such fixed tuples is Fm,r(x)=A(xk)d=A(xm/d)d.

2.1step 1.2L3algebra

Fix a divisor k of m, and write d=m/k. The rotations with m/gcd⁡(m,r)=k are exactly the integers r=ds with 0≤s<k and gcd⁡(s,k)=1, so [L3] shows that there are φ(k) of them. Step 1.2 therefore gives OGF⁡(Cm)=(1/m)∑k∣mφ(k)A(xk)m/k.

3.1step 2.1algebra

Summing step 2.1 over all m≥1 and writing m=dk yields OGF⁡(CYC⁡(A))=∑k≥1(φ(k)/k)∑d≥1A(xk)d/d. Because A(0)=0, every degree receives contributions from only finitely many pairs (k,d), so this regrouping is coefficientwise finite.

4.1step 3.1L4∎

Applying [L4] with u=−A(xk) gives ∑d≥1A(xk)d/d=log⁡(1/(1−A(xk))). Substituting this into step 3.1 gives the stated cycle formula.

Depends on

Used by

Dependency tree · two levels

35 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources