trureturing — Discovering truth

bibkey: ballotkimberlingmoses2017polynomialtrees
authors: Christian Ballot, Clark Kimberling and Peter J. C. Moses
year: 2017
title: Linear Recurrences Originating From Polynomial Trees
doi: 10.1080/00150517.2017.12427731
url: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf
claim: "Table 5 conjectures an eventual generation recurrence with coefficients 3, -3, 1 for the polynomial tree modulo x^2 - 2x + 1."
strata_touched:
  - D5/S3/Combinatorics/PolynomialTrees/BallotKimberlingMosesDoubleRootGeneration
license: citation-only
triage: anchor

Verified locator

DOI: 10.1080/00150517.2017.12427731

Source: https://www.fq.math.ca/Papers1/55-5/BallotKimberlingMoses.pdf

The Fibonacci Quarterly 55(5), pp. 15–27. Published journal PDF SHA-256: ddb8c9e8f4ed843b6150670e0a1f0e1a9f0222028d2f6b0a5d1be6ef73703981. A source arXiv identifier has not been located. The quotations below transcribe mathematical typesetting from the published PDF.

Source statements

Section 1, printed p. 15: root, operations, and generations.

Let $T^{\ast }$ be the set of polynomials in $x$ generated by these rules: $0\in T^{\ast }$, and if $p\in T^{\ast }$, then $p+1\in T^{\ast }$ and $xp\in T^{\ast }$. We regard $T^{\ast }$ 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^2\}$$ $$g(4)=\{4,3x,2x+1,2x^2,x+2,x^2+x,x^2+1,x^3\},$$ and so on, as in Figure 1.

Section 1, printed p. 17: polynomial-form reduction and duplicate deletion.

The rest of this article concerns subtrees of $T^{\ast }$, which appear in various guises, which we shall call (1) polynomial form, (2) numeric form; and (3) tuple form. For the first of these, suppose that $$q(x)=x^m-q_{m-1}{x}^{m-1}-\cdots -q_{1}x-q_0$$ is a fixed polynomial of degree $m\ge 1$. Then the substitution of $$q_{m-1}{x}^{m-1}+\cdots +q_{1}x+q_0$$ for $x^m$ throughout $T^{\ast }$ produces a labeling of $T^{\ast }$ that includes duplicates. We consider two methods for their removal. In the first, the order in which the substitutions in each generation $g(n)$ are made is “top-to-bottom”; i.e., with reference to Figure 1, starting at $n$ and proceeding down to $x^{n-1}$. The other order is “bottom-to-top”. The two trees that result need not be isomorphic, as we shall see in Section 2. For the top-to-bottom order, we denote the resulting tree by $T(q(x))$. The bottom-to-top tree we denote by $T_b(q(x))$. Note that $T(q(x))$ can be regarded as $T^{\ast }\mathrm{mod}q(x)$.

The distinction from the numeric tree is explicit in the next paragraph:

If $r$ is a zero of an irreducible polynomial $q(x)$, then $T(r)$ is isomorphic to $T(q(x))$, and $T_b(r)$ is isomorphic to $T_b(q(x))$. If $r$ is a zero of a reducible polynomial, then $T(r)$ is isomorphic to a subtree of $T(q(x))$, and $T_b(r)$ is isomorphic to a subtree of $T_b(q(x))$.

The generation-count notation is specified on the same page:

Much of the paper henceforth studies the sequence $(G_n{)}_{n\ge 0}$, where $G_n=|g(n)|$ and $g(n)$ is the $n$th generation of the tree $T(r)$, for various $r$.

Section 5 applies this generation notation to the polynomial choices $q(x)$ in its tables; the selected object is the polynomial form, not evaluation at its repeated root $r=1$.

Section 5, printed p. 23: open status and the complete selected row.

Recalling that $q(x)$ in Example 4 is simply $x^2-2$, it is natural to discover that for other choices of $q(x)=x^2-q_{1}x-q_0$, the resulting generations $g(n)$ appear to have linearly recurrent cardinality sequences $(G_n)$. 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.

Table 5, caption “Linear recurrences for $(G_n)$”, selected row (the three cells, in column order):

For each $q(x)$ in Table 5, an unspecified but compelling number of terms satisfying the conjectured recurrence were checked.

Scope

The selected row concerns polynomial remainders modulo (x − 1)², with repeated labels removed and the zero root counted at generation zero. It concerns the whole individual Table 5 row. The families requiring k > 2 do not include this case. Literature-screen completeness and absence of another published settlement remain ASSUMED-UNVERIFIED; the partial screen is specified in the problem statement.

The exact-arithmetic checker is in trureturing-experiments, commit 2962a068f496f8cf04ab18cfb52ecbc1dd319504, file check.py, SHA-256 af584d951450cc7b2b36bfbcba32add83575dca091ade00b280f816c271409f6. The command python3 docs/reports/ballot-kimberling-moses-t5/check.py exits 0: entire remainder and pair shells agree through depth 100 (166751 points, 101 shell counts, recurrence indices 3–100, zero mismatches; ALL_CHECKS_OK). These finite computations do not establish the unbounded recurrence.