Let generate a multiplicative semigroup 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 is at most for all sufficiently large . 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 . 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.
- Erdős, Some applications of graph theory to number theory, p. 82
- Erdős, A survey of problems in combinatorial number theory, pp. 102–104
- Erdős Problem 951 and its historical and claim records
- July 2026 finite-extremum report
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 .
Ordinary primes and separation
Let consist of the ordinary primes which are absent from . Let be the integers whose prime factors all lie outside . Multiplicative closure gives . Any noninteger and a pair satisfying contradict separation.
Theorem 1. Under either of the hypotheses or , all elements of are integers and for every . 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 is irrational. For a finite , write and . Consider and . Restricting to any given class modulo , the fractional parts of are equidistributed. Thus the asymptotic count with both coprime to is . The convergent reciprocal sum gives a uniform positive lower bound .
The integers divisible by a prime in number at most . The map is injective because . The same upper bound for the images, with in place of , counts the whose is divisible by an omitted prime outside . Choose so the sum of these two upper bounds is at most , and then let grow. The surviving pairs give .
Rational elements when the omitted primes have relative density zero
Take in lowest terms with . Choose if both are odd and . Otherwise choose . In either case and . The positive solutions of are parameterised, after a possible shift of the parameter, by two primitive linear forms and . For , let count the roots of modulo . Then , and for . The choice of ensures this at 2 even if both forms have odd leading coefficient. It suffices to show that for some the two forms are both -free.
Put
The prime number theorem and partial summation show that for fixed , and . Consequently , , and 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 at most two classes are deleted and the number deleted is strictly less than , then for an interval of length and sifting range , with a sufficiently small absolute constant, the count is between
where is the product of the retained residue proportions. Indeed, use sieve level and the uniform dimension-two product bound from Mertens’ theorem, since the deletion density is at most and at most at 2. The total interval remainder is bounded by . 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 . Sifting by the primes in up to leaves at least . Take a fixed . The survivors that fail at some with can be counted separately in the at most two roots modulo . In each root the interval for the new variable has length . The still-present restrictions up to have the same local proportions, because is invertible at each of those small primes. The upper sieve gives a bound of order per root. Summing over this range gives
It remains to handle . Write first. Then for a constant depending on the forms, and itself is -free because for large . Primitivity of gives . Thus runs in one class modulo , say . The other form is , an integral linear form in . For an upper bound, sieve the interval by all primes up to for the primality of , and by up to for the absence of those prime factors in the other form. The interval has length at most and can be enlarged to that length. The primality restriction is valid since , and the upper-sieve range condition holds since .
For every the local factor of this new sieve is . If , the zero condition on is one residue class. Its overlap with the zero condition on the other form is exactly as for , because multiplication by is invertible modulo . If , the fixed prime residue is nonzero modulo and the other form has one zero residue, just as in the original sieve. For , there is only the primality condition, which erases one class for and none for . Thus the product for this sieve is exactly
Let . Summing the upper bound over coprime to and -free, the sum of is bounded by the Euler product over outside and coprime to . For large , both and exceed every prime factor of , whose factors cancel in the resulting ratio. Mertens’ theorem then gives a total main-term bound
The two forms can be interchanged, and the summed remainders are . Since and for relative-density-zero , the two large-prime counts total with an absolute constant once is fixed. Fix sufficiently small that this large-prime bound and the medium-prime error leave a positive number of survivors. For any such ,
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 the density passing a finite set of sieving primes is the corresponding product of , uniformly bounded below away from zero as the set grows. The union bound for the remaining primes gives . Choose the finite set first, then let increase. This proves the rational part under either hypothesis.
If contains only integers, the valuation vectors for the generators at most are linearly independent over the rationals, because an integer relation would equate products with distinct exponent vectors. They are supported on the primes at most , 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 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 , infinitely many have both and in . 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 such that every separated system with any noninteger element satisfies
Indeed, suppose the omitted-prime count is at most for all large , where will be a small absolute constant. Partial summation gives, for fixed,
The product is bounded below by a negative power of , so all the power-saving remainders still vanish relative to the main term. For the irrational argument take , and for the rational argument take the defined above. In both, , since the rational local factors differ from by a factor whose product converges to a positive limit. Fix the small-prime threshold exponent so the lower sieve is at least in both proofs. Fix the large-prime upper-sieve exponent (the exponent of ) small enough in both and then choose . The cancellation of the factors of in the rational proof and the uniform lattice sieve in the irrational proof give an absolute constant , independent of and , multiplying the bound
For the rational proof this follows by bounding by and by . For the irrational proof use . First fix with . With this choice, fix the medium-prime sieve exponent (the exponent of ) small enough in both arguments. The combined medium-prime main term is bounded by an absolute constant times
because each omitted prime costs at most a fixed multiple of . Choose so the medium-prime term is at most to leading order and the large-prime term is at most to leading order when . 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 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 remains open.