Erdős 699: finite three-prime cofactor bounds by CRT strips

The checker and certificate prove the following finite statement. It concerns integer factorizations, not bad binomial triples.

Let $134\le n\le10^{1000}$, put $h=n-6$, and choose

Suppose

where the exponents are nonnegative integers and the cofactors are positive integers. Then

except for the configurations explicitly listed in the certificate. There are 208 exceptional configurations on 68 rows. Their largest row is

The factorization need not use the full valuation at each prime. The positions may coincide. The requirement that one position be zero comes from the proved row-zero restriction in the index-six and index-seven applications.

The computation uses 55 anchors and 2,783 exact boundary triples. It does not enumerate the rows up to the height cap.

The stronger exponent $33/50$

A second certificate uses the same algorithm and proves

for $262\le n\le10^{3000}$, except for 4,531 configurations on 1,224 explicitly listed rows. It uses 395 anchors and 2,101,496 exact boundary triples. The largest exceptional row has 157 decimal digits.

There are only 114 exceptional rows greater than $10^{53}$. At each of these rows, the direct product checker computes the full maximal valuations at two, three, and five, choosing the smallest cofactor in the event of a tie. The retained product certificates prove

at every one of those rows. This therefore holds for every selection of maximal-valuation positions on those rows.

Away from the listed exceptions, the triple exponent $33/50$, together with a pair exponent $2/5$ on the other two primes, gives the same product exponent $53/50$. If those two positions coincide, their two cofactors already have product at least $n-6$, so the pair bound follows directly. The triple certificate and the 114 direct product checks consequently supply the product estimate above $10^{53}$ once the three required pair estimates have also been checked on the range in question.

The slab inequality

Fix a rational exponent $\delta=r/s<2/3$ and positions in $[0,D]$. At an exponent anchor put

for three distinct primes. Let $n_0\in[0,M)$ be the CRT solution to

Define $u_{p,0}$ to be the least positive representative of $(n_0-r_p)/P$ modulo $QR$. In particular, when all positions are zero and $n_0=0$, take $u_{p,0}=QR$.

If a later exponent triple has first power $Pp^A$, and its positive cofactor is $u_p'$, then

Let $\mu_p$ be the minimum of $u_{p,0}$ over the allowed position patterns. Consequently

certifies every exponent with $0\le A\le A_0$, independently of the increases at the other two primes. Indeed (1) gives

so $u_p'\ge(n-r_p)^{r/s}\ge(n-D)^{r/s}$.

Thus each anchor can certify up to three coordinate slabs. Their complement is a single orthant, obtained by raising exactly those coordinate lower bounds whose slabs were proved. Every comparison in (1) is integer arithmetic; floating logarithms only propose step counts, subsequently checked exactly.

Minimal CRT rows suffice

Every nonminimal positive CRT solution has $n\ge M$. Therefore

For $\delta=61/100$, $D=6$, and $h\ge64$,

because $64^{17}\ge2^{100}$. Hence at least one cofactor is at least $h^{61/100}$. Only $n_0$ can be exceptional. The all-zero position pattern has $n_0=0$, which is outside the physical height range; all its positive solutions are covered by this argument.

If any prime power is at most six, its cofactor is at least $h/6$. For $h\ge128$ this is at least $h^{61/100}$, since $128^{39}\ge6^{100}$. Thus the exponent search can begin with powers $8,9,25$, and the claimed row range begins at $128+6=134$.

For general $r/s<2/3$, the code chooses a power of two $H$ satisfying

The ratio $h^{3(s-r)}/(h+D)^s$ is increasing, since it is the product $h^{2s-3r}(h/(h+D))^s$ of two increasing positive functions. Thus the first comparison handles every nonminimal CRT solution with $h\ge H$; the second handles any prime power at most $D$. For $r/s=33/50$ and $D=6$, the two exact comparisons hold at $H=256$, giving row start 262.

Exact boundary planes

Suppose no slab is available at an anchor. Remove its three boundary planes, with shared edges assigned to the first plane containing them. On the plane with first power fixed at $P$, a violation implies

Therefore both other prime powers are less than

This leaves an explicit finite exponent box on the plane. At each exponent triple in that box, compute the CRT row for each position pattern, and test its three cofactors by the exact inequality

Record every violation inside the specified height range. Increasing all three anchor exponents by one then leaves precisely the unprocessed orthant. This procedure terminates when one anchor power exceeds the height cap.

There is a useful exact shortcut on a boundary plane with row bound $L$. If the other two powers satisfy $QR>L$, only their minimal two-prime CRT solution can lie in the interval. For each signed difference $d$ with $0<|d|\le D$, compute

The possible rows are $n=X+t$, where $t,r_\ell=t+d\in[0,D]$. Testing $n\bmod P\le D$ supplies the remaining position, and the requirement that one position be zero is checked directly. When $d=0$, the first positive physical row is at least $QR>L$, so there is nothing to test. This shortcut gives exactly the same minimal CRT rows as the three-prime calculation while avoiding most divisions and large power comparisons.

Both retained computations use $7^3-6^3=127$ allowed position patterns. As a targeted implementation check, an independent enumeration of the exponent box through $10^4$ reproduced all 121 exceptional configurations on 37 rows returned by the strip computation at that cap. The corresponding check for exponent $33/50$ reproduced all 304 configurations on 90 rows.

The retained exceptional rows are inputs to a subsequent binomial argument. An exception to this cofactor inequality is not itself a counterexample to Erdős problem 699.

Run the checker with the pinned dependencies, including gmpy2, installed in the repository's .venv/:

.venv/bin/python \
  wiki/research/erdos_699/computations/erdos_699_triple_prime_power_strips.py \
  --cap 1000 --exponent 61/100

To reproduce the stronger certificate, add --cap 3000 --exponent 33/50, set --output to a path under the ignored repository tmp/, and compare the result with the retained _066_3000.json certificate on its mathematical fields.