Erdős 699: finite-range prime-pair certificates

P699 research · Erdős problem 699 · Small-index bounds · Interval certificates

For each pair in the table, let $a,b\ge0$ and $u,v\ge1$ be integers, and set

The exact certificate proves

with the following thresholds. No coprimality or maximal-prime-power condition is imposed on $u,v$.

The checker enumerates prime-power exponents and bounded differences. Its retained output contains all these exceptional minimal solutions and their heights. The calculation does not enumerate binomial rows or columns. It supplies stronger pair inequalities throughout an already bounded range, for use in a complete interval proof. This first table makes no assertion above $10^{976}$; the longer range needed at index 21 is recorded separately below.

Why only minimal solutions need checking

Write $P=p^a$, $Q=q^b$, $M=\max(u,v)$, and more generally let the allowed difference be $D$. The primes $p,q$ are distinct, so $\gcd(P,Q)=1$.

If $\min(P,Q)\le D$, then $M\ge h/D$, and hence $M^3\ge h$ whenever $h^2\ge D^3$. For $D=24$, every $h\ge118$ meets this condition. This also covers zero exponents. If $x=y$, coprimality gives $(u,v)=k(Q,P)$ for a positive integer $k$, so $M^2\ge h$ and again $M^3\ge h$.

It remains to consider $P,Q>D$ and a nonzero signed difference $d=Pu-Qv$, with $|d|\le D$. There is a unique solution

The assumptions $P,Q>D$ imply $1\le v_0<P$. Every positive solution with this difference has the form

For $k\ge1$, we have $M\ge\max(P,Q)$, whereas

Consequently only $(u_0,v_0)$ can violate (1). The minimal solution for $-d$ is $(Q-u_0,P-v_0)$, so testing the positive differences $1,\ldots,D$ and these complementary solutions covers both signs.

Since $P\le x$ and $Q\le y$, the height cap bounds both prime powers. The retained calculation therefore includes every possible exponent: $793$ powers of $17$, $763$ of $19$, $3242$ of $2$, $937$ of $11$, $716$ of $23$, $1396$ of $5$, $1154$ of $7$, and $2045$ of $3$. Powers at most $D$ have already been handled uniformly. For all other powers the procedure tests the minimal solutions, retains only those with $\max(x,y)\le10^{976}$, and records every failure of $M^3\ge h$. The threshold $H$ is the larger of $118$ and one plus the largest recorded exceptional height. This proves (1).

The exceptional records can repeat a height when that height admits several prime-power decompositions. For example, $2^{10}\cdot24=2^{11}\cdot12=2^{12}\cdot6=2^{13}\cdot3$ is checked in all four forms. The certificate requires no restriction that a chosen prime power be the full component of its integer.

Exact filters and modular inverses

Put $A=\max(P,Q)$ and $B=\min(P,Q)$. A violating solution satisfies

Thus $M^2<B$, and necessarily

The program rejects an exponent pair only when integer bit lengths already prove the opposite inequality. If $\ell(z)$ denotes the bit length of a positive integer, then $2^{\ell(z)-1}\le z<2^{\ell(z)}$. In particular,

This is a sufficient rejection test; no approximation to logarithms is used. Similarly, $u^2\ge P$ proves $u^3\ge Pu\ge h$, and $v^2\ge Q$ proves $v^3\ge Qv\ge h$. The first test is sometimes settled immediately by the safe bit-length comparison $2(\ell(u)-1)\ge\ell(P)$; otherwise the program multiplies the integers exactly.

For a fixed $Q$, all inverses of successive powers of $p$ are computed without repeated extended Euclidean calculations. Start with $I=1$, the inverse of $p^0$ modulo $Q$. Choose $0\le k<p$ so that $I+kQ$ is divisible by $p$, and replace

If the old $I$ is the inverse of $p^{a-1}$, (6) is the inverse of $p^a$ modulo $Q$. Moreover $1\le I<Q$ is preserved. The recurrence is performed for every exponent, including powers skipped because they are at most $D$.

Use in the interval proof

For an index $i\le25$, choose maximal positions $r_p,r_q$ in $\{0,\ldots,i-1\}$ and write

Their difference is at most $24$, their smaller height is at least $n-i+1$, and their larger height is at most $n$. Therefore (1) gives

Equivalently, putting $z_p=\log u_p/\log(n-i+1)$, the pair contributes the exact constraint $\max(z_p,z_q)\ge1/3$. These constraints can be combined with the existing prime-pair inequalities when bounding the small-prime part of $\binom ni$ throughout an integer interval. Coincident maximal positions are included by the $x=y$ argument above.

The finite-range inequalities and an independently established infinite tail have separate roles: the tail bounds the remaining rows by $10^{976}$, and (7) strengthens the inequalities used to exclude intervals inside that bound. This note alone does not assert the completion of any particular interval partition.

To reproduce the ten certificates from the repository root:

.venv/bin/python wiki/research/erdos_699/computations/erdos_699_finite_prime_pairs.py --cap 976 --difference 24

The longer range for index 21

The same proof and checker also cover differences at most $20$ and heights at most $10^{1732}$. The second retained certificate gives the following lower thresholds $H$:

Thus every edge in this second table applies to the selected numerator positions of an index-21 row whenever $319\,354\le n\le10^{1732}$. The common interval cutoff $1\,771\,595$ is larger and also accommodates the original explicit BFT table. Reproduce this second table under the ignored repository tmp/ with:

mkdir -p tmp/erdos699
.venv/bin/python wiki/research/erdos_699/computations/erdos_699_finite_prime_pairs.py \
  --pairs 17,19 2,17 5,17 7,17 2,3 2,5 3,5 3,7 5,7 11,13 \
  --cap 1732 --difference 20 \
  --output tmp/erdos699/erdos_699_finite_prime_pairs_21.json

Compare the regenerated file with the retained one on its mathematical fields; elapsed times differ between runs.

Completing the five-prime graph for index 13

Five further certificates cover differences at most $12$ and heights at most $10^{1732}$:

Combine these with the five pairs among $2,3,5,7$ already present in the index-21 table. The resulting ten edges form the complete graph on $\{2,3,5,7,11\}$. All its one-third cofactor constraints hold for an index-13 row whenever $39\,059\,469\le n\le10^{1732}$.

The retained extra certificates are reproduced under the ignored repository tmp/ by:

mkdir -p tmp/erdos699
.venv/bin/python wiki/research/erdos_699/computations/erdos_699_finite_prime_pairs.py \
  --pairs 2,7 2,11 3,11 5,11 7,11 --cap 1732 --difference 12 \
  --output tmp/erdos699/erdos_699_finite_prime_pairs_13_extra.json

Compare the regenerated file with the retained one on its mathematical fields; elapsed times differ between runs.