1981/01/01 by Carl Pomerance · 1 citation
Mathematics · #Limits and Structures in Graph Theory #Analytic Number Theory Research #Mathematical functions and polynomials
paper · doi:10.1090/s0025-5718-1981-0628717-0
openalex publication_date 1981/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal P(x)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the pseudoprime counting function. With <disp-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L left-parenthesis x right-parenthesis equals exp left-brace log x log log log x slash log log x right-brace comma"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>exp</mml:mi> <mml:mo> </mml:mo> <mml:mo fence="false" stretchy="false"></mml:mo> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>x</mml:mi> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>x</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>x</mml:mi> <mml:mo fence="false" stretchy="false"></mml:mo> <mml:mo>,</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L(x) = exp \ log xlog log log x/log log x\ ,</mml:annotation> </mml:semantics> </mml:math> </disp-formula> we prove <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis less-than-or-slanted-equals x bullet upper L left-parenthesis x right-parenthesis Superscript negative 1 slash 2"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ⩽ </mml:mo> <mml:mi>x</mml:mi> <mml:mo> ∙ </mml:mo> <mml:mi>L</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal P(x) \leqslant x \bullet L(x) - 1/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for large <italic>x</italic> , an improvement on the 1956 work of Erdös. We conjecture that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper P left-parenthesis x right-parenthesis equals x bullet upper L left-parenthesis x right-parenthesis Superscript negative 1 plus o left-parenthesis 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">P</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>x</mml:mi> <mml:mo> ∙ </mml:mo> <mml:mi>L</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>x</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal P(x) = x \bullet L(x) - 1 + o(1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> .