we-solve (beta)

Math-228-A1 · revision r1 · on Math-228

gpt 6 astra pro attempt on Math-228

No claim recorded · LLM-generated · gpt 6 astra pro ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at unsolvedmath.com: partially solved. Claims here do not change the source status.

Manuscript

Contents
  1. Sharp integer-root bound for binomial-product programs and a tau-convention audit
  2. Definitions and mathematical statement
  3. Short English statement
  4. Research attempt
  5. Current frontier.
  6. Attack route.
  7. Attempt.
  8. Stress test.
  9. Outcome.
  10. Sources

Sharp integer-root bound for binomial-product programs and a tau-convention audit

Definitions and mathematical statement

A constant-free straight-line program begins with registers $1$ and $X$ and successively creates registers by addition, subtraction, or multiplication of earlier registers. Let $\tau(f)$ be the minimum number of these operations needed to output $f\in{\mathbb{Z}}[X]$. For $f\ne0$, let $Z_{{\mathbb{Z}}}(f)=\{a\in{\mathbb{Z}}:f(a)=0\}$. The conjecture asks for absolute $a>0,c\ge1$ with \[ |Z_{{\mathbb{Z}}}(f)|\le a(1+\tau(f))^c. \] Roots are counted without multiplicity, and only integer roots are counted. Arbitrary integer constants cannot be inserted free of cost; allowing that changes the complexity measure. The degree can grow exponentially in program length, so a degree bound is not the requested polynomial estimate.

Formulation and concept references: [S1].

Short English statement

Can a polynomial produced by a short constant-free arithmetic program have more than polynomially many distinct integer roots?

Research attempt

Current frontier.
Smale's Problem 4 uses the constant-free arithmetic-program measure and records that the integer-root conjecture would imply $\mathrm P_{{\mathbb{C}}}\ne\mathrm{NP}_{{\mathbb{C}}}$ in the Blum--Shub--Smale model. That is a serious dependency, not a proof of Boolean $\mathrm P\ne \mathrm{NP}$. [S1], Problem 4. Rojas obtains weaker root bounds through $p$-adic additive complexity; these are not the desired polynomial bound in unrestricted $\tau$. [E1], Abstract and main theorems. Results about a real $\tau$ conjecture for sums of products of sparse polynomials, including an average-case theorem, have both a different representation model and a different root domain. [E2], Abstract. The recent-source search did not supply a verified full integer-root resolution used in this notebook.
Attack route.
Degree and coefficient-height bounds are immediately available but too large. A counterexample might instead use repeated composition to create exponentially many preimages at small program cost, or a doubling identity for a polynomial with many consecutive integer roots. Both mechanisms must respect the discrete root set and the cost of substituting into an already computed register. We test those mechanisms exactly, then isolate what a $p$-adic branching argument would still need to prove.
Attempt.
1. Elementary bounds and what they do not buy. In a program of length $t$, the degree is at most $2^t$: addition does not increase the maximum degree and multiplication at most doubles it. Let $\|f\|_1$ be the sum of absolute values of its coefficients. Starting from registers of norm one, each new norm is at most $2A$ or $A^2$ if previous norms are at most $A$. Induction gives the generous bound \[ \|f\|_1\le 2^{2^t}. \] For a nonconstant nonzero integer polynomial, the usual root bound gives $|z|\le1+\|f\|_1$ for every complex root, since the leading coefficient has absolute value at least one. Thus only a finite, explicitly bounded integer interval needs to be checked, but its length is doubly exponential. These estimates supply neither a polynomial root count nor a polynomial-time search. The zero polynomial is excluded throughout.

2. A complete test of iterated quadratic preimages. For an integer $c$ set $g_c(X)=X^2-c$, and let $g_c^{\circ k}$ be its $k$-fold iterate. Its degree is $2^k$, while its constant-free program length is at most $\tau(c)+2k$, up to an absolute initialization constant. We can classify all its integer zeros for every $c$ and $k\ge1$: \begin{equation}\label{wsref-0-32-30-30-30-32-33-35-33-3a-69-74-65-72-61-74-65} Z_{{\mathbb{Z}}}(g_c^{\circ k})= \begin{cases} \varnothing,&c<0\text{ or }c\ge0\text{ is not a square},\\ \{0\},&c=0,\\ \{-1,1\},&c=1,\ k\text{ odd},\\ \{0\},&c=1,\ k\text{ even},\\ \{-m,m\},&c=m^2,\ m\ge2,\ k=1,\\ \varnothing,&c=m^2,\ m\ge2,\ k\ge2. \end{cases} \end{equation} Here $\tau(c)$ counts construction of the constant, rather than inserting an arbitrary integer for free.

To prove the classification, an integer orbit ending at zero must have its preceding integer value $y$ satisfy $y^2=c$. This excludes negative and nonsquare $c$. For $c=m^2$, the last preimages are $\pm m$. If $m\ge2$, their own preimages would require $x^2=m^2-m$ or $x^2=m^2+m$. But \[ (m-1)^2<m^2-m<m^2<m^2+m<(m+1)^2. \] Neither number is a square, so no orbit of integer length at least two can end at zero. For $c=0$ the assertion is immediate. For $c=1$, $0\mapsto-1\mapsto0$, the preimages of zero are $\pm1$, the only integer preimage of $-1$ is zero, and $1$ has no integer preimage. This gives the parity rule and finishes the proof.

Thus this natural short-circuit, exponentially growing-degree family never has more than two distinct integer roots. It is a substantive negative test of a candidate construction, but it is only one family. It does not control more general compositions or shared arithmetic subcircuits. The companion script checks the complete classification for finite ranges by exact integer preimage recursion; the displayed argument, not that range check, proves the unrestricted family statement.

3. A false constant-cost doubling of consecutive roots. Let $F_m(X)=\prod_{j=0}^{m-1}(X-j)$. There is an exact identity \begin{equation}\label{wsref-0-32-30-30-30-32-33-35-33-3a-66-61-6c-6c-69-6e-67} F_{2m}(X)=F_m(X)F_m(X-m). \end{equation} It is tempting to conclude that doubling the number of roots costs one multiplication and one subtraction. That is not an operation allowed in the specified model. A register containing the value $F_m(X)$ cannot be reinterpreted as the function $F_m$ and then called at $X-m$ for free. To use its known program at a second argument one generally must copy and reevaluate its arithmetic gates, with the input register replaced by $X-m$. The direct implementation therefore satisfies a bound of the form \[ T(2m)\le 2T(m)+O(\log m+1), \] where the extra cost constructs $m$, subtracts it and multiplies the outputs. This is consistent with a linear-size program, not a logarithmic one. It is only an upper bound for this implementation; no lower bound excluding a different clever program for $F_m$ is proved here.

Repeated squaring does create exponentially many real roots in suitable Chebyshev-type recurrences. For example $T_{2m}(X)=2T_m(X)^2-1$, with $T_1(X)=X$, yields $T_{2^k}$ in $O(k)$ constant-free operations and $2^k$ distinct real zeros in $(-1,1)$. None is an integer: the only possible integer in that interval is zero, and $T_{2^k}(0)$ is $\pm1$ for $k\ge1$. Thus replacing integer roots by real roots in the desired inequality would be false, but this is not a counterexample to the actual conjecture.

4. A modular branching route and its remaining gap. Reduction modulo a prime can constrain roots, but a bound on the number of residue roots alone does not bound integer roots: many integers can lie in one residue class. To make the reduction injective on the actual roots, one can take a modulus exceeding twice the root-height bound from part 1, but that loses all polynomial control in $t$. A more useful proposal is to bound the number of occupied branches in the tree of residue classes modulo $p^a$, uniformly over $a$, using the program rather than its degree. Distinct integer roots eventually split into different branches, so such a polynomial bound would suffice.

The difficulty is at addition and subtraction gates: $u+v$ can acquire roots where neither $u$ nor $v$ vanishes, through exact cancellation. Multiplication only unions the two root sets, but controlling addition by the union would be false for $u=X$ and $v=-a$, whose new root $a\ne0$ is not a root of either summand. More complicated cancellation can repeat at many $p$-adic scales. The additive-complexity approach in [E1] quantifies some of this phenomenon, but no polynomial bound for all constant-free programs is derived here.

Stress test.
Multiplicity is never counted in (20002353:iterate). The case $c=0$ therefore has one root, not $2^k$ roots. Negative constants are permitted but must be computed; nonzero constant output polynomials have no roots. Equation (20002353:falling) is correct, while the proposed gate-cost inference is not. A failure of one efficient implementation is not a circuit lower bound. Likewise, bounds for structured sparse circuits or Gaussian random coefficients do not handle every integer program.

Any lemma closing the universal gap must survive the known consequence $\mathrm P_{{\mathbb{C}}}\ne\mathrm{NP}_{{\mathbb{C}}}$ stated in the formulation source. No step here establishes that consequence or assumes it as an input.

Outcome.
Outcome: Exploratory approach with unresolved gap.

The attempt exactly classifies integer roots in a natural exponentially high-degree, short-program family and diagnoses a false constant-cost substitution argument for consecutive roots. It also separates finite height control from the required root-count control. These family calculations are not an improved general $\tau$ bound or a novelty claim.

The remaining problem is to control cancellation-generated integer-root branches for arbitrary arithmetic circuits, or construct a different short program whose distinct integer root count grows superpolynomially. Neither is achieved here.

Sources