Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

The double-root row of Ballot–Kimberling–Moses Table 5

Abstract

The polynomial tree modulo X squared minus 2 X plus 1 has generation sizes satisfying the Table 5 recurrence with coefficients 3, -3, 1 at every index at least 3.

Definition 1.1 (The double-root polynomial).

Formalization. D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.q (✓ std3).

Citation. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Table 5, p. 23, gives the row q(x) = x² − 2x + 1, Gₙ = 1,1,2,4,7,11,16,22,29,37,46, and linear recurrence 3,−3,1. Here X is Polynomial.X over the integers.

Definition 1.2 (The addition child).

Formalization. D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.addChild (✓ std3).

Citation. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Section 1, p. 15: “Let T∗ be the set of polynomials in x generated by these rules: 0 ∈ T∗, and if p ∈ T∗, then p + 1 ∈ T∗ and xp ∈ T∗.” Section 1, p. 17: “Then the substitution of qₘ₋₁xᵐ⁻¹ + ⋯ + q₁x + q₀ for xᵐ throughout T∗ produces a labeling of T∗ that includes duplicates.” “For the top-to-bottom order, we denote the resulting tree by T(q(x)).” “Note that T(q(x)) can be regarded as T∗ mod q(x).” The addition child is the monic remainder of p + 1 modulo q in Polynomial ℤ.

Definition 1.3 (The multiplication child).

Formalization. D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.mulChild (✓ std3).

Citation. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Section 1, p. 15: “Let T∗ be the set of polynomials in x generated by these rules: 0 ∈ T∗, and if p ∈ T∗, then p + 1 ∈ T∗ and xp ∈ T∗.” Section 1, p. 17: “Then the substitution of qₘ₋₁xᵐ⁻¹ + ⋯ + q₁x + q₀ for xᵐ throughout T∗ produces a labeling of T∗ that includes duplicates.” “For the top-to-bottom order, we denote the resulting tree by T(q(x)).” “Note that T(q(x)) can be regarded as T∗ mod q(x).” The multiplication child is the monic remainder of X * p modulo q in Polynomial ℤ.

Definition 1.4 (All labels reached within a given depth).

Formalization. D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.seen (✓ std3).

Citation. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Section 1, p. 15: “Let T∗ be the set of polynomials in x generated by these rules: 0 ∈ T∗, and if p ∈ T∗, then p + 1 ∈ T∗ and xp ∈ T∗.” Section 1, p. 17: “Then the substitution of qₘ₋₁xᵐ⁻¹ + ⋯ + q₁x + q₀ for xᵐ throughout T∗ produces a labeling of T∗ that includes duplicates.” “For the top-to-bottom order, we denote the resulting tree by T(q(x)).” “Note that T(q(x)) can be regarded as T∗ mod q(x).” The finite set seen n contains every distinct label reached in at most n operations, including the zero root. It accumulates the old labels and both child images, so multiplicities and the choice of a parent among equal labels have no effect.

Definition 1.5 (The generation sets).

Formalization. D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.generation (✓ std3).

Citation. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Section 1, p. 15: “We regard T∗ as a tree that grows in successive generations: g(0) = {0}, g(1) = {1}, g(2) = {2,x}, g(3) = {3,2x,x + 1,x²} g(4) = {4,3x,2x + 1,2x²,x + 2,x² + x,x² + 1,x³}, and so on, as in Figure 1.” Section 1, p. 17: “Then the substitution of qₘ₋₁xᵐ⁻¹ + ⋯ + q₁x + q₀ for xᵐ throughout T∗ produces a labeling of T∗ that includes duplicates.” “For the top-to-bottom order, we denote the resulting tree by T(q(x)).” “Note that T(q(x)) can be regarded as T∗ mod q(x).” Generation zero is the zero root. At depth n + 1, set difference removes every label seen at an earlier depth. Finset membership counts a same-generation duplicate once. These are polynomial remainders, without evaluating X at 1.

Definition 1.6 (Generation cardinality).

Formalization. D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.G (✓ std3).

Citation. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Section 1, p. 17: “Much of the paper henceforth studies the sequence (Gₙ)ₙ≥₀, where Gₙ = |g(n)| and g(n) is the nth generation of the tree T(r), for various r.” Section 5 uses these generation counts for polynomial choices q(x). Here G n is the natural-number cardinality of generation n for the selected polynomial tree.

Definition 1.7 (The eventual recurrence).

Formalization. D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.claim (✓ std3).

Citation. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Section 5, p. 23: “Some proofs of the computer-detected recurrences reported in Table 5 and 6 might be challenging. Most of the entries in the column headed “linear recurrence” are conjectured as “eventual”; i.e., the recurrence applies after some unspecified number of initial terms.” The selected Table 5 row is q(x) = x² − 2x + 1 with recurrence coefficients 3,−3,1. Its assertion is the existence of N ≥ 3 such that the displayed recurrence holds for every n ≥ N. All indices and index subtractions are natural numbers; each G value is embedded into the integers before the recurrence arithmetic.

Theorem 1.8 (The recurrence holds from index three).

Proof. Machine-checked in Lean as D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.result (✓ std3). ∎

Resolves. Problems/bkm-double-root (proved) by D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration.result.

Source. Repository-derived.

Acknowledgement. Christian Ballot, Clark Kimberling and Peter J. C. Moses (2017). Linear Recurrences Originating From Polynomial Trees. DOI: 10.1080/00150517.2017.12427731. URL: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf.

Commentary.

Write each reached remainder uniquely as C(a) + C(b) * (X − 1), where a and b are natural numbers. The two children change the coordinates to (a + 1,b) and (a,b + a). After at most n operations the pairs are exactly (0,0), together with 0 < a ≤ n and b ≤ a(n − a). This follows by induction: subtract a from b when b ≥ a, and otherwise decrease a by one. In generation n + 1, the top row consists of (n + 1,0). For each a ≤ n the remaining row is a(n − a) < b ≤ a(n + 1 − a), an interval of exactly a integers. Injectivity of the polynomial labels therefore gives G(n) = 1 + the sum of a over a < n, including the separate zero-root case. Its consecutive differences equal n, so its third finite difference vanishes. Taking N = 3 proves the assertion.

References