Shapiro’s conjecture

Let 1<a1<a2<⋯1\lt a_1\lt a_2\lt\cdots generate a multiplicative semigroup GG containing 1. Assume the values belonging to distinct nonnegative, finitely supported exponent vectors differ by at least 1. Shapiro’s question, recorded by Erdős, asks whether the generator count A(x)A(x) is at most π(x)\pi(x) for all sufficiently large xx. The cutoff is allowed to depend on the whole sequence.

Status as of 2026-11-20

Erdős’s 1969 paper asks a finite version. The 1977 and 1980 surveys ask the real-generator question and discuss the relationship with Beurling’s generalised primes. Known finite counterexamples refute the interpretation requiring the inequality at every xx. Their extensions produce infinite separated systems with a violation at a fixed cutoff. The wiki claim records, the finite-case research report, the survey sources and searches for subsequent eventual results yielded no resolution for arbitrarily large cutoffs.

Lagarias studies a rigidity question for integer Beurling systems under bounded gaps and proves structural results about omitted primes. The argument below uses gaps strictly smaller than one to rule out nonintegral elements when the system contains sufficiently many ordinary primes. It imposes no upper bound on gaps in GG.

Ordinary primes and separation

Let EE consist of the ordinary primes which are absent from GG. Let SES_E be the integers whose prime factors all lie outside EE. Multiplicative closure gives SE⊆GS_E\subseteq G. Any noninteger λ∈G\lambda\in G and a pair n,m∈SEn,m\in S_E satisfying 0<|λn−m|<10\lt |\lambda n-m|\lt1 contradict separation.

Theorem 1. Under either of the hypotheses ∑p∈E1/p<∞\sum_{p\in E}1/p\lt\infty or #(E∩[1,x])=o(π(x))\#(E\cap[1,x])=o(\pi(x)), all elements of GG are integers and A(x)≤π(x)A(x)\le\pi(x) for every xx. In particular, any separated system with a noninteger element omits a positive upper proportion of the ordinary primes. The last section shows that this upper proportion is bounded below by an absolute positive constant.

Irrational elements when the omitted reciprocals converge

Suppose λ\lambda is irrational. For a finite E0⊆EE_0\subseteq E, write M=∏p∈E0pM=\prod_{p\in E_0}p and ρ0=φ(M)/M\rho_0=\varphi(M)/M. Consider n≤Xn\le X and m=⌊λn⌋m=\lfloor\lambda n\rfloor. Restricting nn to any given class modulo MM, the fractional parts of λn/M\lambda n/M are equidistributed. Thus the asymptotic count with both n,mn,m coprime to MM is ρ02X\rho_0^2 X. The convergent reciprocal sum gives a uniform positive lower bound ρ0≥ρ=∏p∈E(1−1/p)>0\rho_0\ge\rho=\prod_{p\in E}(1-1/p)\gt0.

The integers n≤Xn\le X divisible by a prime in E\E0E\setminus E_0 number at most X∑p∈E\E01/pX\sum_{p\in E\setminus E_0}1/p. The map n↦mn\mapsto m is injective because λ>1\lambda\gt1. The same upper bound for the images, with λX\lambda X in place of XX, counts the nn whose mm is divisible by an omitted prime outside E0E_0. Choose E0E_0 so the sum of these two upper bounds is at most ρ2X/2\rho^2 X/2, and then let XX grow. The surviving pairs give 0<λn−m<10\lt\lambda n-m\lt1.

Rational elements when the omitted primes have relative density zero

Take λ=a/b>1\lambda=a/b\gt1 in lowest terms with b≥2b\ge2. Choose t=2t=2 if both a,ba,b are odd and 2∈E2\in E. Otherwise choose t=1t=1. In either case 0<t<b0\lt t\lt b and gcd(t,ab)=1\gcd(t,ab)=1. The positive solutions of an−bm=tan-bm=t are parameterised, after a possible shift of the parameter, by two primitive linear forms L1(k)=bk+n0L_1(k)=bk+n_0 and L2(k)=ak+m0L_2(k)=ak+m_0. For p∈Ep\in E, let ν(p)\nu(p) count the roots of L1L2L_1L_2 modulo pp. Then ν(p)<p\nu(p)\lt p, and ν(p)=2\nu(p)=2 for p∤abtp\nmid abt. The choice of tt ensures this at 2 even if both forms have odd leading coefficient. It suffices to show that for some kk the two forms are both EE-free.

Put

W(Y)=∏p∈E,p≤Y(1−1/p),V(Y)=∏p∈E,p≤Y(1−ν(p)/p).W(Y)=\prod_{p\in E,\ p\le Y}(1-1/p),\qquad V(Y)=\prod_{p\in E,\ p\le Y}(1-\nu(p)/p).

The prime number theorem and partial summation show that ∑Yc<p≤Yd,p∈E1/p=o(1)\sum_{Y^c\lt p\le Y^d,\ p\in E}1/p=o(1) for fixed 0<c<d0\lt c\lt d, and ∑p≤Y,p∈E1/p=o(loglogY)\sum_{p\le Y,\ p\in E}1/p=o(\log\log Y). Consequently W(Yd)/W(Yc)→1W(Y^d)/W(Y^c)\to1, W(Y)=(logY)−o(1)W(Y)=(\log Y)^{-o(1)}, and V(Y)/W(Y)2V(Y)/W(Y)^2 tends to a positive constant. Constant multiples in the product cutoffs also have ratio tending to one.

We use the combinatorial fundamental lemma for linear congruences. If at each prime pp at most two classes are deleted and the number deleted is strictly less than pp, then for an interval of length HH and sifting range z≤Hc*z\le H^{c_*}, with c*c_* a sufficiently small absolute constant, the count is between

34HU(z)−O(H2/3)and2HU(z)+O(H2/3),\tfrac34 H U(z)-O(H^{2/3})\qquad\text{and}\qquad 2H U(z)+O(H^{2/3}),

where U(z)U(z) is the product of the retained residue proportions. Indeed, use sieve level H1/2H^{1/2} and the uniform dimension-two product bound from Mertens’ theorem, since the deletion density is at most 2/p2/p and at most 1/21/2 at 2. The total interval remainder is bounded by ∑d≤H1/22ω(d)=O(H1/2logH)\sum_{d\le H^{1/2}}2^{\omega(d)}=O(H^{1/2}\log H). The constants thus do not depend on the individual residues or on the omitted-prime set. A prime with no retained residue gives count zero in the upper-bound uses below.

Fix 0<c<c*0\lt c\lt c_*. Sifting 1≤k≤X1\le k\le X by the primes in EE up to XcX^c leaves at least (3/4−o(1))XV(X)(3/4-o(1))X V(X). Take a fixed 0<δ<min(c,1/10)0\lt\delta\lt\min(c,1/10). The survivors that fail at some p∈Ep\in E with Xc<p≤X1−δX^c\lt p\le X^{1-\delta} can be counted separately in the at most two roots modulo pp. In each root the interval for the new variable has length X/p+O(1)X/p+O(1). The still-present restrictions up to z0=Xc*δ/2z_0=X^{c_*\delta/2} have the same local proportions, because pp is invertible at each of those small primes. The upper sieve gives a bound of order (X/p)V(z0)+(X/p)2/3(X/p)V(z_0)+(X/p)^{2/3} per root. Summing over this range gives

O(XV(z0)∑Xc<p≤X1−δ,p∈E1p+X1−δ/3)=o(XV(X)).O\left(XV(z_0)\sum_{X^c\lt p\le X^{1-\delta},\ p\in E}\frac1p + X^{1-\delta/3}\right)=o(XV(X)).

It remains to handle p>X1−δp\gt X^{1-\delta}. Write L1(k)=hpL_1(k)=hp first. Then h≤CXδh\le C X^\delta for a constant CC depending on the forms, and hh itself is EE-free because CXδ<XcC X^\delta\lt X^c for large XX. Primitivity of L1L_1 gives gcd(h,b)=1\gcd(h,b)=1. Thus pp runs in one class modulo bb, say p=r+bup=r+bu. The other form is (ahp−t)/b(ahp-t)/b, an integral linear form in uu. For an upper bound, sieve the uu interval by all primes up to z1=Xmin(c,c*/4)z_1=X^{\min(c,c_*/4)} for the primality of pp, and by EE up to z1z_1 for the absence of those prime factors in the other form. The interval has length at most O(X/h)O(X/h) and can be enlarged to that length. The primality restriction is valid since p>z1p\gt z_1, and the upper-sieve range condition holds since h=O(Xδ)h=O(X^\delta).

For every q∈Eq\in E the local factor of this new sieve is 1−ν(q)/q1-\nu(q)/q. If q∤bq\nmid b, the zero condition on pp is one residue class. Its overlap with the zero condition on the other form is exactly as for L1,L2L_1,L_2, because multiplication by hh is invertible modulo qq. If q∣bq\mid b, the fixed prime residue rr is nonzero modulo qq and the other form has one zero residue, just as in the original sieve. For q∉Eq\notin E, there is only the primality condition, which erases one class for q∤bq\nmid b and none for q∣bq\mid b. Thus the product for this sieve is exactly

U(z1)=V(z1)∏q≤z1,q∉E,q∤b(1−1/q).U(z_1)=V(z_1)\prod_{q\le z_1,\ q\notin E,\ q\nmid b}(1-1/q).

Let Y=CXδY=C X^\delta. Summing the upper bound over h≤Yh\le Y coprime to bb and EE-free, the sum of 1/h1/h is bounded by the Euler product over q≤Yq\le Y outside EE and coprime to bb. For large XX, both z1z_1 and YY exceed every prime factor of bb, whose factors cancel in the resulting ratio. Mertens’ theorem then gives a total main-term bound

(2+o(1))XV(z1)logYlogz1W(Y)W(z1).(2+o(1))X V(z_1)\frac{\log Y}{\log z_1}\frac{W(Y)}{W(z_1)}.

The two forms can be interchanged, and the summed remainders are Oa,b(X(2+δ)/3)O_{a,b}(X^{(2+\delta)/3}). Since V(z1)∼V(X)V(z_1)\sim V(X) and W(Y)∼W(z1)W(Y)\sim W(z_1) for relative-density-zero EE, the two large-prime counts total O(δXV(X))+o(XV(X))O(\delta X V(X))+o(XV(X)) with an absolute constant once cc is fixed. Fix δ\delta sufficiently small that this large-prime bound and the medium-prime error leave a positive number of survivors. For any such kk,

0<|λL1(k)−L2(k)|=t/b<1.0\lt \left|\lambda L_1(k)-L_2(k)\right|=t/b\lt1.

This excludes the rational noninteger. Convergence of the omitted reciprocal sum does not by itself imply relative prime density zero. For that hypothesis, the rational assertion follows directly from the same local root conditions: among 1≤k≤X1\le k\le X the density passing a finite set of sieving primes is the corresponding product of 1−ν(p)/p1-\nu(p)/p, uniformly bounded below away from zero as the set grows. The union bound for the remaining primes gives Oa,b(X∑p∈E\E01/p+π(CX))O_{a,b}(X\sum_{p\in E\setminus E_0}1/p+\pi(CX)). Choose the finite set E0E_0 first, then let XX increase. This proves the rational part under either hypothesis.

If GG contains only integers, the valuation vectors for the generators at most xx are linearly independent over the rationals, because an integer relation would equate products with distinct exponent vectors. They are supported on the π(x)\pi(x) primes at most xx, which proves the bound in Theorem 1. The same rank argument proves the eventual bound whenever all generators are rational and only finitely many are nonintegers. In that case take xx beyond all prime factors of every exceptional numerator and denominator.

Irrational elements when the omitted primes have relative density zero

Proof using continued-fraction lattices. For every irrational λ>1\lambda\gt1, infinitely many nn have both nn and ⌊λn⌋\lfloor\lambda n\rfloor in SES_E. This excludes every noninteger element under the second hypothesis of Theorem 1.

An absolute lower bound on the omitted proportion

The same sieves give an absolute η0>0\eta_0\gt0 such that every separated system with any noninteger element satisfies

limsupx→∞#(E∩[1,x])π(x)≥η0.\limsup_{x\to\infty}\frac{\#(E\cap[1,x])}{\pi(x)}\ge\eta_0.

Indeed, suppose the omitted-prime count is at most ηπ(x)\eta\pi(x) for all large xx, where η\eta will be a small absolute constant. Partial summation gives, for 0<u<v0\lt u\lt v fixed,

∑Xu<p≤Xv,p∈E1p≤ηlog(v/u)+o(1),W(Xu)W(Xv)≤(v/u)η(1+o(1)).\sum_{X^u\lt p\le X^v,\ p\in E}\frac1p \le\eta\log(v/u)+o(1),\qquad \frac{W(X^u)}{W(X^v)}\le(v/u)^\eta(1+o(1)).

The product W(X)W(X) is bounded below by a negative power of logX\log X, so all the power-saving remainders still vanish relative to the main term. For the irrational argument take V=W2V=W^2, and for the rational argument take the VV defined above. In both, V(Xu)/V(Xv)≤(v/u)2η(1+o(1))V(X^u)/V(X^v)\le(v/u)^{2\eta}(1+o(1)), since the rational local factors differ from (1−1/p)2(1-1/p)^2 by a factor whose product converges to a positive limit. Fix the small-prime threshold exponent cc so the lower sieve is at least (3/4−o(1))XV(X)(3/4-o(1))XV(X) in both proofs. Fix the large-prime upper-sieve exponent c1c_1 (the exponent of z1z_1) small enough in both and then choose δ<min(c,c1,1/10)\delta\lt\min(c,c_1,1/10). The cancellation of the factors of bb in the rational proof and the uniform lattice sieve in the irrational proof give an absolute constant C1C_1, independent of δ,η\delta,\eta and λ\lambda, multiplying the bound

(δ1−ηc1−η+o(1))XV(X).\big(\delta^{1-\eta}c_1^{-\eta}+o(1)\big)XV(X).

For the rational proof this follows by bounding V(z1)/V(X)V(z_1)/V(X) by c1−2η(1+o(1))c_1^{-2\eta}(1+o(1)) and W(Y)/W(z1)W(Y)/W(z_1) by (c1/δ)η(1+o(1))(c_1/\delta)^\eta(1+o(1)). For the irrational proof use W(Y)W(z1)/W(X)2W(Y)W(z_1)/W(X)^2. First fix δ\delta with C1δ<1/8C_1\delta\lt1/8. With this choice, fix the medium-prime sieve exponent c0c_0 (the exponent of z0z_0) small enough in both arguments. The combined medium-prime main term is bounded by an absolute constant times

(c0−2ηηlog((1−δ)/c)+o(1))XV(X),\big(c_0^{-2\eta}\eta\log((1-\delta)/c)+o(1)\big)XV(X),

because each omitted prime costs at most a fixed multiple of XV(z0)/pX V(z_0)/p. Choose η0>0\eta_0\gt0 so the medium-prime term is at most XV(X)/8XV(X)/8 to leading order and the large-prime term is at most XV(X)/4XV(X)/4 to leading order when η=η0\eta=\eta_0. These choices are independent of the fixed noninteger element. Its parameters affect the cutoff from which the inequalities apply. Both proofs yield a surviving pair and contradict separation. This proves the asserted lower bound on the limsup.

A fixed-number-field bound

Proof using prime ideals and the logarithmic unit lattice. If the generators are algebraic integers in one fixed real number field and the other conjugates have absolute value at most one, their count is at most (1−cK)π(x)(1-c_K)\pi(x) eventually. The proof only needs multiplicative independence within this class.

Open step

The theorem constrains attempts to extend a finite nonintegral counterexample by including almost all ordinary primes. The appearance of a positive proportion of omitted primes does not compare the total of the noninteger and integer generalised generators. A proof of the eventual inequality or a single counterexample violating it for arbitrarily large xx remains open.