Journal of the American Mathematical Society · 2006 · 34 citations · 5 references
An old question of Erdős asks if there exists, for each number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, a finite set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of integers greater than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and residue classes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis n right-parenthesis left-parenthesis mod n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mtext> </mml:mtext> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>mod</mml:mtext> </mml:mrow> <mml:mtext> </mml:mtext> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(n)~(\textrm {mod}~n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of upper S"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>S</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n\in S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> whose union is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb Z</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We prove that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma-summation Underscript n element-of upper S Endscripts 1 slash n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mo>∑</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>S</mml:mi> </mml:mrow> </mml:munder> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\sum _{n\in S}1/n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is bounded for such a covering of the integers, then the least member of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is also bounded, thus confirming a conjecture of Erdős and Selfridge. We also prove a conjecture of Erdős and Graham, that, for each fixed number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K greater-than 1"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">K>1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the complement in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb Z</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of any union of residue classes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis n right-parenthesis left-parenthesis mod n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mtext> </mml:mtext> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>mod</mml:mtext> </mml:mrow> <mml:mtext> </mml:mtext> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(n)~(\textrm {mod}~n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, for distinct <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of left-parenthesis upper N comma upper K upper N right-bracket"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>,</mml:mo> <mml:mi>K</mml:mi> <mml:mi>N</mml:mi> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">n\in (N,KN]</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, has density at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript upper K"> <mml:semantics> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>K</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">d_K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> sufficiently large. Here <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript upper K"> <mml:semantics> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>K</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">d_K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a positive number depending only on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Either of these new results implies another conjecture of Erdős and Graham, that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a finite set of moduli greater than <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, with a choice for residue classes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis n right-parenthesis left-parenthesis mod n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mtext> </mml:mtext> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>mod</mml:mtext> </mml:mrow> <mml:mtext> </mml:mtext> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(n)~(\textrm {mod}~n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n element-of upper S"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>S</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n\in S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which covers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper Z"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">Z</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbb Z</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, then the largest member of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> cannot be <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altt
5