Erdős 699: cutoff 35 and the cubic case

P699 research · Erdős problem 699 · Earlier effectivity reduction

Call $(n,i,j)$ admissible if $1\le i<j\le n/2$, and bad if no prime $p\ge i$ divides both $\binom ni$ and $\binom nj$. All conclusions below concern this original, non-strict threshold.

Further small-index progress. The cutoff-nine proof excludes seven and every $i\ge9$. The four indices $4,5,6,8$ still lack effective row bounds here. The cubic results below are unchanged.

Further cubic progress. The follow-up note strengthens the computational exclusions to $n\le10^{19}$ and every row with $v_2(n)\le48$. It also gives an endpoint divisibility criterion, bounds on individual prime-power components, and an infinite family of good columns. Global cubic finiteness remains unproved. The original computation through $10^{12}$ is retained below.

Results of this investigation.

1. There are no bad triples with $i\ge35$, or with $i=29$. This is a computer-assisted consequence of the retained algebraic arguments: a certified interval calculation handles $i=29$ and $35\le i\le905$, and the earlier theorem handles $i\ge906$.
2. A bad triple with $i=3$ must satisfy

An exact search using these reductions excludes every $n\le10^{12}$. This does not prove that the remaining cubic exceptions are finite. 3. The least possible degree-to-multiplicity ratio for a nonzero polynomial vanishing uniformly on the six Kummer points $\Delta_3$ is exactly $9/4$. The manuscript's exponent argument would require a ratio below $2$, so optimizing that uniform certificate cannot resolve $i=3$.

Cutoff statement. For every admissible $(n,i,j)$ with $i=29$ or $i\ge35$, there is a prime $p\ge i$ dividing both binomial coefficients. The proof combines the finite certificates below with the published prime-gap computation and the $i\ge906$ result.

The deductions and computations here are repository work. Their novelty has not been assessed. The algebraic inputs come from the retained detailed manuscript and its reconstruction. The previous $i\ge906$ calculation remains an input for the infinite tail.

1. A sharper symmetric discriminant bound

Put

Every coefficient of

is divisible by $D$. Indeed,

and cancellation of the gcd shows that $D$ divides the product on the right after removing $\binom nj$. Consequently $D^{2i-2}\mid\operatorname{Disc}R$ for $i\ge2$.

Cancel the displayed factors of $\binom ji$ in the manuscript's Jacobi discriminant formula, and reverse the index in its $j$-product. This gives the symmetric identity

Since $(j-r+1)(c-r+1)\le n^2/4$ and $n-r+1\le n$,

Thus, without any additional restriction on $j$,

This retains much more than the earlier bound with $(4n/27)^{i/4}$. If $n\ge L$ and

then the product in (3) is at least $\gamma_i(L)$.

2. Two necessary size bounds under badness

Let $S_i=\{p:p<i\}$, $s_i=\pi(i-1)$, and write $\binom ni=U_i(n)V_i(n)$, where $U_i$ is supported on $S_i$ and $V_i$ on primes at least $i$. Under badness, $G$ divides $U_i$.

For $i\ge5$ put

The reconstructed fat-point divisor gives $V_i(n)^m<n^{3A}/4^A$: pair the vertical and horizontal factors and use $(j-r)(c-r)\le n^2/4$. Together with (3), this gives the two necessary inequalities

The fat-point bound is useful at large $n$ even when $i/4\le s_i$. The discriminant bound is often stronger near the lower end of the search.

Kummer's formula also gives

The first $v_p(i)$ summands vanish, so

For $i=29$ and every $35\le i\le905$, $\lambda_i-s_i>0$. Combining (4) and (6) therefore gives an explicit last row. When $i/4-s_i>0$, the discriminant bound supplies another last row, and we take the smaller certified bound. The checker rounds upward to a power of ten and includes that endpoint in the interval being checked.

3. Excluding the entire remaining interval

Let $P_i$ be the lower endpoint of the first prime gap longer than $i$. If $n<P_i$, a prime lies in $(n-i,n]$ and divides both required binomial coefficients. Thus a bad triple must have $n\ge P_i$. The retained prime-gap records come from the authors' published computation and data. Their range covers all the lower endpoints used here. The JSON records the source URL, publication and retrieval date of the downloaded table.

For each index, use $L=P_i$ in (4) and let $B_i$ be the inclusive upper bound from (6). It remains to exclude the finite interval $[P_i,B_i]$. The upper bounds can be enormous—for example, the checker uses $10^{99}$ at $i=35$—so it does not enumerate rows.

For an integer interval $[a,b]$, define

The indicator is one exactly when at least one integer in $[a,b]$ can satisfy the corresponding residue condition in (5). Therefore, for every $n\in[a,b]$,

An interval contains no bad row if

Both lower bounds increase with $n$, so checking them at the left endpoint is enough. If (9) is not certified, bisect the interval into disjoint integer intervals and continue. Every accepted leaf has a rigorous positive margin; an unexcluded singleton or an exhausted node budget causes the checker to fail rather than report a proof.

The complete checker completed for $i=29$ and all $35\le i\le905$. Its recorded output contains 872 index records and 399,713 certified leaf intervals. The smallest certified logarithmic margin is

at $i=49$. It uses 60-digit Decimal intervals with outward rounding; floating point guides subdivision but cannot certify a leaf. The exact valuation bound was also checked against factorial valuations in 37,829 bounded cases. Each index record includes a hash of its interval partition for reproducibility.

Combining this completed calculation with the retained $i\ge906$ theorem proves the stated cutoff $i\ge35$, together with the additional case $i=29$. The statement is computer-assisted and uses the cited prime-gap computation.

4. What fails at index three

At $i=3$, the small-prime set is just $\{2\}$, and $U_3(n)\le n$ is already effective. It cannot be replaced by a uniform smaller power of $n$: for every $h\ge2$,

The finiteness argument would need $V_3(n)<n^\rho$ with $\rho<2$, so that $U_3(n)\gg n^{3-\rho}$ grows faster than $n$. This is an exponent obstruction, separate from the ineffective constant at the other small indices.

In fact the uniform fat-point method has the following exact limitation.

Proposition. If a nonzero polynomial of degree $d$ vanishes to order at least $m$ at every point of

then $d/m\ge9/4$. Equality is attained.

Proof. View these points as the three vertices and three edge midpoints of the triangle with barycentric coordinates $X,Y,Z=2-X-Y$. Multiplying the six transforms of the polynomial under permutations of $X,Y,Z$ makes it symmetric, multiplying both $d$ and the required $m$ by six. Thus we may assume that the three outer lines $X=0,Y=0,Z=0$ occur with the same multiplicity $a$, and the three inner lines $X=1,Y=1,Z=1$ with the same multiplicity $b$.

Remove those six line factors. The remaining polynomial $H$ has degree $D=d-3a-3b$, has none of those lines as a component, and has multiplicities at least $m-2a$ at the vertices and $m-a-2b$ at the midpoints. Bézout on an outer line and an inner line, respectively, gives

Adding shows $a\ge5m-2d$. For any degree-$D$ polynomial, the sum of its multiplicities at three noncollinear points is at most $2D$. To see this, send the three points to the coordinate vertices in the projective plane: every nonzero homogeneous monomial must have its three exponents at most $D$ minus the corresponding multiplicities, and its exponents sum to $D$. Applying this to the midpoints of $H$ gives

Consequently $5m-2d\le(2d-3m)/3$, or $d\ge9m/4$. Finally,

has degree nine and multiplicity four at each of the six points. This attains equality. $\square$

This proposition rules out fixing the manuscript's cubic exponent argument by replacing its uniform vanishing polynomial with a better one. Additional information about the labels or the small-prime part is needed.

5. Elementary cubic exclusions

For an odd prime $q$ dividing $n-t$, $t\in\{0,1,2\}$, write $q^a\Vert n-t$. Such a prime divides $\binom n3$ except when $q=3$ and $a=1$. If it does divide $\binom n3$, badness and Kummer imply the full prime-power restriction

For $q=3$ and $a\ge2$, this uses the absence of carries in all the first $a$ digits, even though the denominator $3!$ removes one factor of $3$.

The central column is good. Suppose $n$ is even and $n\ge8$. There is an odd prime divisor $q$ of $n-1$ which divides $\binom n3$: otherwise $n-1$ would be $1$ or $3$. For $j=n/2$,

so $q\mid\binom nj$ by Lucas. Thus a bad triple has $j<n/2$.

Odd rows are good. If $n$ is odd and $v_3(n)\ne1$, applying (11) at $t=0$ to all prime powers of $n$ gives $n\mid j$, impossible. If $v_3(n)=1$, it gives $(n/3)\mid j$, so $j=n/3$. But $n-2$ has a prime divisor $q\ge5$, and (11) would require $j\equiv r\pmod q$ for $r\in\{0,1,2\}$. The equation $3j=n$ then forces $q\mid3r-2\in\{-2,1,4\}$, again impossible.

Rows $n\equiv2\pmod4$ are good. Their odd part is $n/2$. If $v_3(n)\ne1$, (11) gives $(n/2)\mid j$, forcing the already excluded central column. If $v_3(n)=1$, it gives $(n/6)\mid j$, so $j\in\{n/6,n/3,n/2\}$. The central column is good. For $j=n/3$, any prime divisor $q\ge5$ of $n-1$ would have to divide $3r-1\in\{-1,2\}$, where $r=0$ or $1$. For $j=n/6$, every prime power $q^a\Vert n-1$ would have to divide $6r-1\in\{-1,5\}$. As $n-1$ is odd and coprime to $3$, this forces $n-1\in\{1,5\}$, giving no admissible triple.

We have therefore proved that a bad cubic triple must have $4\mid n$ and $j<n/2$.

6. A strong restriction on the odd part of a bad row

Write $n=2^h u$ with $h\ge2$ and $u$ odd. Then

For the cubic orbit polynomial, direct expansion of the cubic discriminant gives

Since $V_3(n)$ divides every coefficient under badness, $V_3(n)^4\mid\operatorname{Disc}R$. Also $8\mid\operatorname{Disc}R$ when $4\mid n$: if $j,c$ are odd, $(j-1)(c-1)$ is divisible by $8$, and $(n-2)^2$ by $4$; if $j,c$ are even, $j^2c^2(n-2)^2$ is divisible by $64$. Thus in both cases $32\mid F$, and division by $12$ leaves a factor $8$. As $V_3(n)$ is odd,

Using $jc\le n^2/4$ and $(j-1)(c-1)\le(n-2)^2/4$ gives

Since $n\ge8$,

Substituting $n=2^h u$ proves $3u^3<2^h$, completing (1). Equivalently, the odd part satisfies $u<(n/3)^{1/4}$; for each fixed $h$ there is an explicit finite list of possible rows.

The missing step for global finiteness is an upper bound on $h$ or another argument that excludes the family as $h\to\infty$. Condition (1) alone still allows arbitrarily large powers of two, so it is not a finite-set reduction.

7. Exhaustive cubic verification through one trillion

The cubic checker generates every row allowed by (1) up to the requested limit. It factors the three numerator factors by exact trial division, intersects (11) by CRT, and tests the full Lucas conditions on any surviving columns.

At $n\le10^{12}$ there are exactly 2,184 rows requiring this search. None has even one column $4\le j<n/2$ satisfying all the full prime-power restrictions (11). Thus there are no bad cubic triples in that entire range. See the recorded output.

The implementation was compared with direct binomial gcds for both thresholds $p\ge3$ and $p>3$ through $n=200$, and the cubic discriminant identity was checked exactly on those admissible pairs. As positive controls it detects the strict-threshold exceptions $(n,i,j)=(10,3,5),(28,3,14),(244,3,122),(2188,3,1094)$ and correctly rejects them as counterexamples to the original threshold $p\ge3$.

Reproduction and current remaining cases

Both commands use Python 3.11 or later and only the standard library:

python3 wiki/research/erdos_699/computations/erdos_699_i_ge_35.py
python3 wiki/research/erdos_699/computations/erdos_699_i_eq_3.py --limit 1000000000000

The earlier effectivity note supplies effective finiteness at $i=28,31,34$, without instantiated numerical constants. At that stage it left 27 ineffective indices, $\{4,\ldots,27,30,32,33\}$. The subsequent prime-pair argument lowers the cutoff to $26$, also excludes $17,23$, and reduces the ineffective list to nine indices. The earlier reduction recorded here was:

• $i=3$, only in the sparse family (1), with all rows through $10^{12}$ excluded;
• a finite possible exceptional set at $4\le i\le34$, $i\ne29$.

No global finiteness or nonexistence assertion is proved for the first item.