Introduction
Let
f ( x ) = ∑ j ≥ 0 a j x j ∈ Q [ [ x ] ] , a j ≠ 0 , f n ( x ) = ∑ j = 0 n a j x j . f(x)=\sum_{j\geq0}a_jx^j\in\mathbb{Q}[[x]],\qquad a_j\ne0,\qquad f_n(x)=\sum_{j=0}^n a_jx^j. f ( x ) = j ≥ 0 ∑ a j x j ∈ Q [[ x ]] , a j = 0 , f n ( x ) = j = 0 ∑ n a j x j . We study the Galois group over Q \mathbb{Q} Q n n n f n f_n f n n n n S n \mathfrak{S}_n S n A n \mathfrak{A}_n A n
The classical example is the exponential series. Schur proved in 1930 that
E n ( x ) = ∑ j = 0 n x j j ! , n ≥ 1 , E_n(x)=\sum_{j=0}^n\frac{x^j}{j!},\qquad n\geq1, E n ( x ) = j = 0 ∑ n j ! x j , n ≥ 1 , has Galois group A n \mathfrak{A}_n A n 4 ∣ n 4\mid n 4 ∣ n S n \mathfrak{S}_n S n [40 ] . Symmetric groups therefore occur in three quarters of the degrees and alternating groups in one quarter. Coleman’s proof [11 ] uses Newton polygons to obtain permutations in the Galois group from the prime divisibility of the factorial denominators. Related arguments apply to generalized Laguerre polynomials [21 ] .
On the other hand, the geometric series gives a different example. Its Taylor polynomial is ( x n + 1 − 1 ) / ( x − 1 ) (x^{n+1}-1)/(x-1) ( x n + 1 − 1 ) / ( x − 1 ) n ≥ 4 n\geq4 n ≥ 4 S n \mathfrak{S}_n S n A n \mathfrak{A}_n A n
Katz and Rivin [26 Questions 1.1–1.2] ask whether this happens for every power series with nonzero rational coefficients. More precisely, they ask whether the three proportions always converge and, when they all converge, whether the third limit must be zero or one.
Our first result answers both questions negatively. We prove that for any set of degrees B ⊆ { 3 , 4 , … } B \subseteq\{3,4,\ldots\} B ⊆ { 3 , 4 , … } n ≥ 3 n \ge3 n ≥ 3 n n n S n \mathcal{S}_n S n n ∈ B n \in B n ∈ B n ≥ 3 n \ge3 n ≥ 3 n − 1 n-1 n − 1 S n − 1 \mathcal{S}_{n-1} S n − 1
We then give conditions on the prime divisors of the coefficients that force the symmetric group to occur in density one. For nonintegral binomial powers, an exact discriminant formula determines the exceptional degrees and gives their asymptotic number. For the central-binomial and Catalan generating functions, we determine the groups in every degree over Q \mathbb{Q} Q
Prescribing the degrees with symmetric group
We call f n f_n f n n n n f f f P ∈ F [ X ] P \in F[X] P ∈ F [ X ] F F F Gal F ( P ) \operatorname{Gal}_F(P) Gal F ( P ) F F F P P P n n n S n \mathcal{S}_n S n G n = Gal Q ( f n ) G_n=\operatorname{Gal}_{\mathbb{Q}}(f_n) G n = Gal Q ( f n )
s f ( N ) = 1 N # { 3 ≤ n ≤ N : G n = S n } , s_f(N)=\frac{1}{N}\#\{3\le n\le N:G_n=\mathcal{S}_n\}, s f ( N ) = N 1 # { 3 ≤ n ≤ N : G n = S n } , a f ( N ) = 1 N # { 3 ≤ n ≤ N : G n = A n } , a_f(N)=\frac{1}{N}\#\{3\le n\le N:G_n=\mathcal{A}_n\}, a f ( N ) = N 1 # { 3 ≤ n ≤ N : G n = A n } , o f ( N ) = 1 N # { 3 ≤ n ≤ N : f n is other } . o_f(N)=\frac{1}{N}\#\{3\le n\le N:f_n\text{ is other}\}. o f ( N ) = N 1 # { 3 ≤ n ≤ N : f n is other } . Here a section is called other if it has a repeated root, or if it is separable and its group is neither S n \mathcal{S}_n S n A n \mathcal{A}_n A n S ( f ) S(f) S ( f ) A ( f ) A(f) A ( f ) O ( f ) O(f) O ( f )
The construction also controls polynomials formed from finite consecutive blocks of coefficients. More precisely, for 0 ≤ r < s 0\le r<s 0 ≤ r < s
f r , s ( X ) = ∑ j = r s a j X j − r , K r , s = its splitting field over Q . (1) f_{r,s}(X)=\sum_{j=r}^{s}a_jX^{j-r},\qquad K_{r,s}=\text{its splitting field over }\mathbb{Q}. \tag*{(1)} f r , s ( X ) = j = r ∑ s a j X j − r , K r , s = its splitting field over Q . (1) We call f r , s f_{r,s} f r , s normalized segment , and a proper segment when r ≥ 1 r\ge1 r ≥ 1 X r X^r X r s − r s-r s − r I I I ( r , s ) (r,s) ( r , s )
[ ∏ ( r , s ) ∈ I K r , s : Q ] = ∏ ( r , s ) ∈ I [ K r , s : Q ] , \left[\prod_{(r,s)\in I}K_{r,s}:\mathbb{Q}\right]=\prod_{(r,s)\in I}[K_{r,s}:\mathbb{Q}], ( r , s ) ∈ I ∏ K r , s : Q = ( r , s ) ∈ I ∏ [ K r , s : Q ] , where the product of fields means their compositum in a fixed algebraic closure. Finally, 1 ⊕ S n − 1 1\oplus\mathcal{S}_{n-1} 1 ⊕ S n − 1 S n \mathcal{S}_n S n n − 1 n-1 n − 1
Theorem A. Let B ⊆ { 3 , 4 , … } B\subseteq\{3,4,\ldots\} B ⊆ { 3 , 4 , … } ( ϵ n ) n ≥ 2 (\epsilon_n)_{n\ge2} ( ϵ n ) n ≥ 2
f ( z ) = 1 + z + ∑ n ≥ 2 a n z n , a n ∈ Q > 0 , f(z)=1+z+\sum_{n\ge2}a_nz^n,\qquad a_n\in\mathbb{Q}_{>0}, f ( z ) = 1 + z + n ≥ 2 ∑ a n z n , a n ∈ Q > 0 , with the following properties.
(i) We have G 2 = S 2 G_2=\mathfrak{S}_2 G 2 = S 2 n ≥ 3 n\geq3 n ≥ 3
G n = { S n , n ∈ B , 1 ⊕ S n − 1 , n ∉ B . (2) G_n=
\begin{cases}
\mathfrak{S}_n, & n\in B,\\
1\mathbin{\oplus}\mathfrak{S}_{n-1}, & n\notin B.
\end{cases} \tag*{(2)} G n = { S n , 1 ⊕ S n − 1 , n ∈ B , n ∈ / B . (2) In the second case, the unique rational root is a negative integer and the remaining factor is irreducible of degree n − 1 n-1 n − 1
(ii) For every n ≥ 2 n\geq2 n ≥ 2
0 < a n < min { ε n , 2 − n 2 } , a n − 1 2 > 4 a n − 2 a n . (3) 0<a_n<\min\{\varepsilon_n,2^{-n^2}\},\qquad a_{n-1}^2>4a_{n-2}a_n. \tag*{(3)} 0 < a n < min { ε n , 2 − n 2 } , a n − 1 2 > 4 a n − 2 a n . (3) The function has order zero and infinitely many zeros, all simple and negative. Every f r , s f_{r,s} f r , s s − r s-r s − r
(iii) Every proper segment of degree at least two has full symmetric group:
Gal ( K r , s / Q ) = S s − r ( 1 ≤ r ≤ s − 2 ) . (4) \operatorname{Gal}(K_{r,s}/\mathbb{Q})=\mathfrak{S}_{s-r}\qquad(1\leq r\leq s-2). \tag*{(4)} Gal ( K r , s / Q ) = S s − r ( 1 ≤ r ≤ s − 2 ) . (4) All fields K r , s K_{r,s} K r , s 0 ≤ r ≤ s − 2 0\leq r\leq s-2 0 ≤ r ≤ s − 2 Q \mathbb{Q} Q
Moreover, if B B B ( ε n ) (\varepsilon_n) ( ε n )
The coefficients a n a_n a n n ≥ 2 n\geq2 n ≥ 2 ρ ( f ) = lim sup R → ∞ log log M f ( R ) / log R \rho(f)=\limsup_{R\to\infty}\log\log M_f(R)/\log R ρ ( f ) = lim sup R → ∞ log log M f ( R ) / log R M f ( R ) = max ∣ z ∣ = R ∣ f ( z ) ∣ M_f(R)=\max_{|z|=R}|f(z)| M f ( R ) = max ∣ z ∣ = R ∣ f ( z ) ∣
If B B B δ \delta δ
( S ( f ) , A ( f ) , O ( f ) ) = ( δ , 0 , 1 − δ ) . (S(f),A(f),O(f))=(\delta,0,1-\delta). ( S ( f ) , A ( f ) , O ( f )) = ( δ , 0 , 1 − δ ) . If B B B s f ( N ) s_f(N) s f ( N ) 0 ≤ α ≤ β ≤ 1 0\leq\alpha\leq\beta\leq1 0 ≤ α ≤ β ≤ 1
A simple example with convergent proportions is the rational function
h 2 ( x ) = 1 + x 2 1 − x = 1 + x + 2 x 2 + 2 x 3 + ⋯ , ( S ( h 2 ) , A ( h 2 ) , O ( h 2 ) ) = ( 1 / 2 , 0 , 1 / 2 ) . (5) h_2(x)=\frac{1+x^2}{1-x}=1+x+2x^2+2x^3+\cdots,\qquad(S(h_2),A(h_2),O(h_2))=(1/2,0,1/2). \tag*{(5)} h 2 ( x ) = 1 − x 1 + x 2 = 1 + x + 2 x 2 + 2 x 3 + ⋯ , ( S ( h 2 ) , A ( h 2 ) , O ( h 2 )) = ( 1/2 , 0 , 1/2 ) . (5) Its even sections have symmetric group, whereas every odd section of degree at least three has the root − 1 -1 − 1
An arithmetic condition for density one
We next consider polynomials obtained from ∑ j = 0 s s x j / ( s + j ) \sum_{j=0}^{s} sx^j/(s+j) ∑ j = 0 s s x j / ( s + j ) s ∈ Q ∖ Z s\in\mathbb{Q}\setminus\mathbb{Z} s ∈ Q ∖ Z n + C n+C n + C C ≥ 0 C\geq0 C ≥ 0 n + C n+C n + C
We state the result over a number field F F F R F R_F R F F F F R Q = 1 R_{\mathbb{Q}}=1 R Q = 1 N ( a , b , C , F ) N(a,b,C,F) N ( a , b , C , F ) (25) . For frequencies over F F F s f , F ( N ) , a f , F ( N ) , o f , F ( N ) s_{f,F}(N),a_{f,F}(N),o_{f,F}(N) s f , F ( N ) , a f , F ( N ) , o f , F ( N ) S F ( f ) , A F ( f ) , O F ( f ) S_F(f),A_F(f),O_F(f) S F ( f ) , A F ( f ) , O F ( f ) Q \mathbb{Q} Q F F F
Theorem B. Fix s = a / b ∈ Q ∖ Z s=a/b\in\mathbb{Q}\setminus\mathbb{Z} s = a / b ∈ Q ∖ Z b ≥ 2 b\ge2 b ≥ 2 C ≥ 0 C\ge0 C ≥ 0 n ≥ 1 n\ge1 n ≥ 1
R n ( x ) = ∑ j = 0 n u n , j s s + j x j , u n , j ∈ Q × . R_n(x)=\sum_{j=0}^{n}u_{n,j}\frac{s}{s+j}x^j,\qquad u_{n,j}\in\mathbb{Q}^{\times}. R n ( x ) = j = 0 ∑ n u n , j s + j s x j , u n , j ∈ Q × . Suppose that every u n , j u_{n,j} u n , j p p p p > n + C p>n+C p > n + C F F F R n R_n R n A n \mathcal{A}_n A n n ≥ N ( a , b , C , F ) n\ge N(a,b,C,F) n ≥ N ( a , b , C , F ) n n n S n \mathcal{S}_n S n ε > 0 \varepsilon>0 ε > 0
# { 1 ≤ n ≤ X : Gal F ( R n ) ≠ S n } ≪ s , C , F , ε X 1 / 2 + ε . (6) \#\{1\le n\le X:\operatorname{Gal}_F(R_n)\ne\mathcal{S}_n\}\ll_{s,C,F,\varepsilon}X^{1/2+\varepsilon}. \tag*{(6)} # { 1 ≤ n ≤ X : Gal F ( R n ) = S n } ≪ s , C , F , ε X 1/2 + ε . (6) The threshold and implied constant are uniform in the multipliers.
Thus, beyond the stated threshold, the only possible groups are A n \mathcal{A}_n A n S n \mathcal{S}_n S n n n n ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) F F F
For example, the theorem applies to bounded nonzero integer multiples of the coefficients of
∑ j ≥ 0 s ( s + j ) ( j ! ) r x j , r ∈ Z ≥ 0 . \sum_{j\ge0}\frac{s}{(s+j)(j!)^r}x^j,\qquad r\in\mathbb{Z}_{\ge0}. j ≥ 0 ∑ ( s + j ) ( j ! ) r s x j , r ∈ Z ≥ 0 . § 4.5 gives the resulting Kummer and error-function examples, as well as extensions to polynomial multipliers. A smaller explicit threshold for half-integral s s s § 8 .§ 2 .
Binomial and Catalan polynomials
We consider certain polynomials to extract more information. Fix s ∈ Q ∖ Z s\in\mathbb{Q}\setminus\mathbb{Z} s ∈ Q ∖ Z ( 1 − x ) − s (1-x)^{-s} ( 1 − x ) − s
B s , n ( x ) = ∑ j = 0 n ( s ) j j ! x j , ( s ) 0 = 1 , ( s ) j = s ( s + 1 ) ⋯ ( s + j − 1 ) . B_{s,n}(x)=\sum_{j=0}^{n}\frac{(s)_j}{j!}x^j,\qquad(s)_0=1,\qquad(s)_j=s(s+1)\cdots(s+j-1). B s , n ( x ) = j = 0 ∑ n j ! ( s ) j x j , ( s ) 0 = 1 , ( s ) j = s ( s + 1 ) ⋯ ( s + j − 1 ) . An affine change of variable puts them in the family of Theorem B. Once the Galois group contains A n \mathcal{A}_n A n A n \mathcal{A}_n A n S n \mathcal{S}_n S n F × 2 = { u 2 : u ∈ F × } F^{\times2}=\{u^2:u\in F^\times\} F × 2 = { u 2 : u ∈ F × } F F F
Theorem C. Fix s = a / b ∈ Q ∖ Z s=a/b\in\mathbb{Q}\setminus\mathbb{Z} s = a / b ∈ Q ∖ Z b ≥ 2 b\ge2 b ≥ 2 F F F n ≥ N ( a , b , 0 , F ) n\ge N(a,b,0,F) n ≥ N ( a , b , 0 , F )
Gal F ( B s , n ) = { A n , n even and ( − 1 ) n / 2 a ( a + b n ) ∈ F × 2 , S n , otherwise . (7) \operatorname{Gal}_F(B_{s,n})=
\begin{cases}
\mathcal{A}_n, & n\text{ even and }(-1)^{n/2}a(a+bn)\in F^{\times2},\\
\mathcal{S}_n, & \text{otherwise}.
\end{cases} \tag*{(7)} Gal F ( B s , n ) = { A n , S n , n even and ( − 1 ) n /2 a ( a + bn ) ∈ F × 2 , otherwise . (7) There is an explicitly computable constant c s , F ≥ 0 c_{s,F}\ge0 c s , F ≥ 0
# { 1 ≤ n ≤ X : Gal F ( B s , n ) ≠ S n } = c s , F X + O s , F ( 1 ) . (8) \#\{1\le n\le X:\operatorname{Gal}_F(B_{s,n})\ne\mathcal{S}_n\}=c_{s,F}\sqrt{X}+O_{s,F}(1). \tag*{(8)} # { 1 ≤ n ≤ X : Gal F ( B s , n ) = S n } = c s , F X + O s , F ( 1 ) . (8) The constant vanishes exactly when every sufficiently large section has symmetric group. It is positive for every s > 0 s>0 s > 0 ( 1 − x ) − s (1-x)^{-s} ( 1 − x ) − s ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) F F F
For positive nonintegral s s s 1 / 2 1/2 1/2 (39) computes c s , F c_{s,F} c s , F F F F Q \mathbb{Q} Q Corollary 4.10 gives a closed formula and determines exactly which negative parameters have infinitely many alternating degrees.
Here the exponent s s s [18 ] study the complementary problem in which the degree is fixed and a positive integral exponent varies. The identity (37) also expresses B s , n B_{s,n} B s , n n n n § 4 (see also [34 ] ).
For the central-binomial generating function ( 1 − 4 x ) − 1 / 2 (1-4x)^{-1/2} ( 1 − 4 x ) − 1/2 [36 Section 4.1] . It also proves Sun’s criterion for the existence of an irreducible reduction of the monic reciprocal polynomial [45 part (ii)] .
Theorem D. Let C n ( x ) = ∑ j = 0 n ( 2 j j ) x j C_n(x)=\sum_{j=0}^{n}\binom{2j}{j}x^j C n ( x ) = ∑ j = 0 n ( j 2 j ) x j n ≥ 1 n\ge1 n ≥ 1
Gal Q ( C n ) = { A n , n = 2 r ( r + 1 ) for an integer r ≥ 1 , S n , otherwise. (9) \operatorname{Gal}_{\mathbb{Q}}(C_n)=
\begin{cases}
\mathcal{A}_n, & n=2r(r+1)\text{ for an integer }r\ge1,\\
\mathcal{S}_n, & \text{otherwise.}
\end{cases} \tag*{(9)} Gal Q ( C n ) = { A n , S n , n = 2 r ( r + 1 ) for an integer r ≥ 1 , otherwise. (9) Over a number field F F F n ≥ R F n\ge R_F n ≥ R F
Gal F ( C n ) = { A n , n even and ( − 1 ) n / 2 ( 2 n + 1 ) ∈ F × 2 , S n , otherwise. (10) \operatorname{Gal}_{F}(C_n)=
\begin{cases}
\mathcal{A}_n, & n\text{ even and }(-1)^{n/2}(2n+1)\in F^{\times2},\\
\mathcal{S}_n, & \text{otherwise.}
\end{cases} \tag*{(10)} Gal F ( C n ) = { A n , S n , n even and ( − 1 ) n /2 ( 2 n + 1 ) ∈ F × 2 , otherwise. (10) The monic reciprocal x n C n ( 1 / x ) x^nC_n(1/x) x n C n ( 1/ x ) n n n 2 r ( r + 1 ) 2r(r+1) 2 r ( r + 1 ) 1 / n 1/n 1/ n
In particular, in the exceptional degrees 2 r ( r + 1 ) 2r(r+1) 2 r ( r + 1 ) Q \mathbb{Q} Q
The Catalan numbers c j = ( 2 j j ) / ( j + 1 ) c_j=\binom{2j}{j}/(j+1) c j = ( j 2 j ) / ( j + 1 ) ( 1 − 1 − 4 x ) / ( 2 x ) (1-\sqrt{1-4x})/(2x) ( 1 − 1 − 4 x ) / ( 2 x ) [41 Theorem 1.1] proved that every nonconstant Taylor polynomial of this function is irreducible over Q \mathbb{Q} Q [45 part (i)] .
Theorem E. For every n ≥ 1 n\ge1 n ≥ 1
P n ( x ) = ∑ j = 0 n c j x j P_n(x)=\sum_{j=0}^{n}c_jx^j P n ( x ) = j = 0 ∑ n c j x j has Galois group S n \mathcal{S}_n S n Q \mathbb{Q} Q F F F
Gal F ( P n ) = S n ( n ≥ R F ) . \operatorname{Gal}_{F}(P_n)=\mathcal{S}_n \qquad(n\ge R_F). Gal F ( P n ) = S n ( n ≥ R F ) . In particular, ( 1 − 1 − 4 x ) / ( 2 x ) (1-\sqrt{1-4x})/(2x) ( 1 − 1 − 4 x ) / ( 2 x ) ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) F F F
Both the central-binomial and Catalan generating functions are algebraic of degree two. Their Taylor polynomials nevertheless have the full symmetric group over Q \mathbb{Q} Q n 2 + n + 5 n^2+n+5 n 2 + n + 5 x n P n ( 1 / x ) x^nP_n(1/x) x n P n ( 1/ x )
Methods and further results
The construction in Theorem A chooses one coefficient at a time. Reversing the next Taylor polynomial gives
X n f n ( 1 / X ) = g n ( X ) + a n , g n ( X ) = ∑ j = 0 n − 1 a j X n − j . (11) X^nf_n(1/X)=g_n(X)+a_n,\qquad g_n(X)=\sum_{j=0}^{n-1}a_jX^{n-j}. \tag*{(11)} X n f n ( 1/ X ) = g n ( X ) + a n , g n ( X ) = j = 0 ∑ n − 1 a j X n − j . (11) The coefficients already chosen determine g n g_n g n a n a_n a n [8 Theorem 13] preserves these conditions outside a finite set of choices. These conditions give the full product of the symmetric groups before specialization. Hilbert irreducibility then gives the required groups for all segments ending at the new degree and makes their splitting fields disjoint from the preceding fields. Adjoining one root before specialization gives the alternative with one rational root. The specializations can be made small and positive, so Hutchinson’s coefficient inequalities [23 ] give the assertions about real zeros.
The simultaneous control of proper segments is related to the conjecture of Bary-Soroker and Ben-Porath [2 Conjecture 1] for proper segments of the exponential series. They prove simultaneous probabilistic results, and Weinbaum [47 Theorem 1.1] proves density-one symmetry for each fixed positive shift. The all-degree problem for proper segments of the fixed exponential series remains open. Earlier questions about irreducibility of Taylor polynomials arose in Katz’s 2009 Princeton course; see [9 Introduction] . Chambert-Loir also constructs sections with highly multiple roots [9 Example 3.7] .
For Theorem B, suitable primes larger than the degree give a Newton polygon with two primitive edges. The corresponding local factors have degrees j j j n − j n-j n − j [32 Theorem 3.3] then gives containment of A n \mathcal{A}_n A n [22 ] bounds the number of degrees in which the discriminant can be a square in the fixed number field. For binomial polynomials, the exact discriminant formula reduces the exceptional count to quadratic congruences.
The Catalan proof begins with the transitivity supplied by Seki’s irreducibility theorem. In sufficiently large degree, local inertia rules out all possible block systems except a partition into two blocks. We extend Seki’s trace argument from rational factors to possible Galois blocks. The resulting congruences and size bounds force the sums of roots in the two blocks to be distinct rational integers, which is incompatible with transitivity. The classical Jordan–Marggraff theorem [29 Theorem A] then gives the required alternating containment, and an odd inertia permutation gives the symmetric group.
There are also examples with constant term 1 and all other coefficients in { 1 , … , 35 } \{1,\ldots,35\} { 1 , … , 35 } Proposition 2.12 gives, after any finite choice of these coefficients, a computable continuation for which O f ( N ) O_f(N) O f ( N ) [3 Theorems 1(a) and 6] with extensions having many cyclotomic factors. § 7 gives criteria for convergence and shows that convergence cannot be decided uniformly from a program for the rational coefficients. It also gives a finite test when the Galois labels themselves are generated by an automaton.
Organization
§ 2 proves Theorem A and the bounded-coefficient constructions. § 3 gives the local Galois criteria. § 4 proves Theorems B, C, and D; § 5 proves Theorem E. § 6 treats further rational and classical families, and § 7 develops the frequency and computability consequences. The remaining questions are collected in § 7.6 . Appendix § 8 proves the explicit prime estimates.
Acknowledgements
I thank Nicholas M. Katz and Igor Rivin for posing the questions that motivated this work and for encouragement. I am especially grateful to Nicholas M. Katz for his suggestions concerning the rational families ( 1 + N x k ) / ( 1 − x ) (1+Nx^k)/(1-x) ( 1 + N x k ) / ( 1 − x )
AI Declaration
OpenAI’s ChatGPT was used in the preparation and revision of this paper to assist with mathematical arguments and to prepare and run exact-arithmetic code for the finite certificates. The October 2026 revisions used GPT-6 Astra Pro. Responsibility for the mathematical claims, references, and final text rests with the author.
Prescribing all sections and segments
Specialization and simultaneous covers
A polynomial g g g d ≥ 2 d \ge2 d ≥ 2 Morse if g ′ g' g ′ d − 1 d-1 d − 1 g g g L / Q ( T ) L/\mathbb{Q}(T) L / Q ( T ) regular over Q \mathbb{Q} Q L ∩ Q = Q L \cap\mathbb{Q} = \mathbb{Q} L ∩ Q = Q
Lemma 2.2. Let P ( X , U ) ∈ Q ( U ) [ X ] P(X,U) \in\mathbb{Q}(U)[X] P ( X , U ) ∈ Q ( U ) [ X ] Q ( U ) \mathbb{Q}(U) Q ( U ) Q \mathbb{Q} Q G G G E / Q E/\mathbb{Q} E / Q u u u P ( X , u ) P(X,u) P ( X , u ) G G G E E E Q \mathbb{Q} Q u u u
Proof. Let L L L P P P Q ( U ) \mathbb{Q}(U) Q ( U ) E ∗ / Q E^*/\mathbb{Q} E ∗ / Q E / Q E/\mathbb{Q} E / Q
Gal ( L E ∗ / Q ( U ) ) = G × Gal ( E ∗ / Q ) . \operatorname{Gal}(LE^*/\mathbb{Q}(U)) = G \times\operatorname{Gal}(E^*/\mathbb{Q}). Gal ( L E ∗ / Q ( U )) = G × Gal ( E ∗ / Q ) . After removing finitely many parameter values, the normalization of the parameter line in L E ∗ LE^* L E ∗ étale Galois cover. At a rational parameter u u u L u E ∗ L_uE^* L u E ∗ L u L_u L u P ( X , u ) P(X,u) P ( X , u ) [42 Proposition 3.3.1] shows that, outside a thin subset of Q \mathbb{Q} Q
[ L u E ∗ : Q ] = ∣ G ∣ [ E ∗ : Q ] . [L_uE^* : \mathbb{Q}] = |G|[E^* : \mathbb{Q}]. [ L u E ∗ : Q ] = ∣ G ∣ [ E ∗ : Q ] . The specialization action on the roots identifies Gal ( L u / Q ) \operatorname{Gal}(L_u/\mathbb{Q}) Gal ( L u / Q ) G G G G G G L u L_u L u E ∗ E^* E ∗ E E E [42 Proposition 3.3.3] ; it uses the splitting-field cover and does not require P P P
Include the poles of the coefficients, the zeros of the discriminant, and the prescribed finite excluded set among the exceptional values. By the integral thin-set estimate [42 Theorem 3.4.4] , the exceptional integers in [ − H , H ] [-H,H] [ − H , H ] O ( H 1 / 2 log H ) O(H^{1/2}\log H) O ( H 1/2 log H )
The next lemma makes the induction possible: the conditions for the next degree exclude only finitely many values of the new coefficient. Its one-polynomial form appears in the proof of [8 Theorem 13] .
Lemma 2.3. Let ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 h 1 , … , h ℓ ∈ C [ X ] h_1,\ldots,h_\ell\in\mathbb{C}[X] h 1 , … , h ℓ ∈ C [ X ] c ∈ C c \in\mathbb{C} c ∈ C h i ( X ) + c X h_i(X) + cX h i ( X ) + c X
Proof. A repeated critical point for the i i i h i ′ ′ ( x ) = 0 h_i''(x)=0 h i ′′ ( x ) = 0 c = − h i ′ ( x ) c=-h_i'(x) c = − h i ′ ( x ) c c c ξ i , j ( c ) \xi_{i,j}(c) ξ i , j ( c )
v i , j ( c ) = h i ( ξ i , j ( c ) ) + c ξ i , j ( c ) . v_{i,j}(c) = h_i(\xi_{i,j}(c)) + c\xi_{i,j}(c). v i , j ( c ) = h i ( ξ i , j ( c )) + c ξ i , j ( c ) . Since h i ′ ( ξ i , j ( c ) ) + c = 0 h_i'(\xi_{i,j}(c)) + c = 0 h i ′ ( ξ i , j ( c )) + c = 0
v i , j ′ ( c ) = ξ i , j ( c ) . v_{i,j}'(c) = \xi_{i,j}(c). v i , j ′ ( c ) = ξ i , j ( c ) . Two critical values of the same polynomial cannot agree identically, because their derivatives are distinct critical points. Suppose that critical values belonging to h i h_i h i h k h_k h k i ≠ k i \ne k i = k ξ ( c ) \xi(c) ξ ( c ) h i ′ − h k ′ h_i' - h_k' h i ′ − h k ′ ξ ( c ) \xi(c) ξ ( c ) h i ′ ( ξ ( c ) ) + c = 0 h_i'(\xi(c)) + c = 0 h i ′ ( ξ ( c )) + c = 0 h i ′ = h k ′ h_i' = h_k' h i ′ = h k ′ h i − h k h_i-h_k h i − h k
For a global finite exceptional set, consider
D ( c , Y ) = ∏ i = 1 ℓ Res X ( h i ′ ( X ) + c , h i ( X ) + c X − Y ) . D(c,Y)=\prod_{i=1}^{\ell}\operatorname{Res}_{X}\left(h_i'(X)+c,h_i(X)+cX-Y\right). D ( c , Y ) = i = 1 ∏ ℓ Res X ( h i ′ ( X ) + c , h i ( X ) + c X − Y ) . Its leading coefficient in Y Y Y c c c Disc Y D ( c , Y ) \operatorname{Disc}_{Y}D(c,Y) Disc Y D ( c , Y ) c c c Y Y Y
Disjoint critical-value sets make the symmetric groups of the individual covers independent. The same independence remains after one root of one polynomial is adjoined to the base field.
Lemma 2.4. Let g 0 , … , g k ∈ Q [ X ] g_0,\ldots,g_k\in\mathbb{Q}[X] g 0 , … , g k ∈ Q [ X ] d i ≥ 2 d_i\ge2 d i ≥ 2 b i b_i b i
(i) The common splitting field of the polynomials g i ( X ) + T g_i(X)+T g i ( X ) + T Q ( T ) \mathbb{Q}(T) Q ( T ) Q \mathbb{Q} Q
∏ i = 0 k S d i (12) \prod_{i=0}^{k}\mathfrak{S}_{d_i} \tag*{(12)} i = 0 ∏ k S d i (12) in its action on their respective root sets.
(ii) For an independent variable R R R
Q g 0 ( X , R ) = g 0 ( X ) − g 0 ( R ) X − R . (13) Q_{g_0}(X,R)=\frac{g_0(X)-g_0(R)}{X-R}. \tag*{(13)} Q g 0 ( X , R ) = X − R g 0 ( X ) − g 0 ( R ) . (13) The common splitting field over Q ( R ) \mathbb{Q}(R) Q ( R ) Q g 0 ( X , R ) , g i ( X ) − g 0 ( R ) ( 1 ≤ i ≤ k ) Q_{g_0}(X,R),\quad g_i(X)-g_0(R)\quad(1\le i\le k) Q g 0 ( X , R ) , g i ( X ) − g 0 ( R ) ( 1 ≤ i ≤ k ) Q \mathbb{Q} Q
S d 0 − 1 × ∏ i = 1 k S d i (14) \mathfrak{S}_{d_0-1}\times\prod_{i=1}^{k}\mathfrak{S}_{d_i} \tag*{(14)} S d 0 − 1 × i = 1 ∏ k S d i (14) in the natural action on each displayed factor. In particular, each factor is irreducible over Q ( R ) \mathbb{Q}(R) Q ( R )
Dividing the respective polynomials by b i b_i b i
Proof. The polynomials g i ( X ) + T g_i(X)+T g i ( X ) + T Q ( T ) \mathbb{Q}(T) Q ( T ) i ≠ j i\ne j i = j Q \mathbb{Q} Q g i − g j g_i-g_j g i − g j T T T
For a single polynomial, part (i) is Hilbert’s theorem [42 Theorem 4.4.1] . The map g i : P C 1 → P C 1 g_i:\mathbb{P}^{1}_{\mathbb{C}}\to\mathbb{P}^{1}_{\mathbb{C}} g i : P C 1 → P C 1
Let H H H (12) and projects onto each factor. The finite branch values in the T T T g i g_i g i g i g_i g i i i i H H H i i i H H H H H H H H H Q \mathbb{Q} Q Q \mathbb{Q} Q
Let L L L α \alpha α g 0 ( X ) + T g_0(X)+T g 0 ( X ) + T (14) , and its fixed field is
Q ( T ) ( α ) = Q ( α ) , T = − g 0 ( α ) . \mathbb{Q}(T)(\alpha)=\mathbb{Q}(\alpha), \qquad T=-g_0(\alpha). Q ( T ) ( α ) = Q ( α ) , T = − g 0 ( α ) . Here α \alpha α Q \mathbb{Q} Q Q ( R ) \mathbb{Q}(R) Q ( R ) α \alpha α R R R g 0 ( X ) + T g_0(X)+T g 0 ( X ) + T Q g 0 ( X , R ) Q_{g_0}(X,R) Q g 0 ( X , R ) g i ( X ) − g 0 ( R ) g_i(X)-g_0(R) g i ( X ) − g 0 ( R ) L L L Q ( R ) \mathbb{Q}(R) Q ( R ) L ∩ Q ‾ = Q L\cap\overline{\mathbb{Q}}=\mathbb{Q} L ∩ Q = Q α \alpha α
Real zeros
The analytic condition in the main theorem is a strict form of Hutchinson’s criterion [23 ] ; see also the discussion in [27 §1] . We include a proof to record simplicity and the finite-segment assertion explicitly.
Lemma 2.6. Let a j > 0 a_j>0 a j > 0 j ≥ 0 j\geq0 j ≥ 0
a j 2 > 4 a j − 1 a j + 1 ( j ≥ 1 ) . (15) a_j^2>4a_{j-1}a_{j+1}\qquad(j\geq1). \tag*{(15)} a j 2 > 4 a j − 1 a j + 1 ( j ≥ 1 ) . (15) Then f ( z ) = ∑ j ≥ 0 a j z j f(z)=\sum_{j\geq0}a_jz^j f ( z ) = ∑ j ≥ 0 a j z j f r , s f_{r,s} f r , s f f f ∑ j ≥ 0 a r + j z j \sum_{j\geq0}a_{r+j}z^j ∑ j ≥ 0 a r + j z j
Proof. Put r k = a k − 1 / a k r_k=a_{k-1}/a_k r k = a k − 1 / a k k ≥ 1 k\geq1 k ≥ 1 r k + 1 > 4 r k r_{k+1}>4r_k r k + 1 > 4 r k
a n ≤ a 0 r 1 − n 4 − n ( n − 1 ) / 2 . (16) a_n\leq a_0r_1^{-n}4^{-n(n-1)/2}. \tag*{(16)} a n ≤ a 0 r 1 − n 4 − n ( n − 1 ) /2 . (16) This proves entire convergence and, by completing the square in the exponent of the majorant, gives log M f ( R ) = O ( ( log R ) 2 ) \log M_f(R)=O((\log R)^2) log M f ( R ) = O (( log R ) 2 ) R → ∞ R\to\infty R → ∞ ρ ( f ) = 0 \rho(f)=0 ρ ( f ) = 0
Set x k = 2 r k x_k=2r_k x k = 2 r k x 0 = 0 x_0=0 x 0 = 0 N ≥ k ≥ 1 N\geq k\geq1 N ≥ k ≥ 1 f N ( − x k ) f_N(-x_k) f N ( − x k ) ( − 1 ) k a k x k k (-1)^ka_kx_k^k ( − 1 ) k a k x k k k k k r k / x k = 1 / 2 r_k/x_k=1/2 r k / x k = 1/2 x k / r k + 1 < 1 / 2 x_k/r_{k+1}<1/2 x k / r k + 1 < 1/2
( − 1 ) k f N ( − x k ) a k x k k ≥ 1 − 1 2 − x k r k + 1 > 0 , (17) \frac{(-1)^kf_N(-x_k)}{a_kx_k^k}\geq1-\frac{1}{2}-\frac{x_k}{r_{k+1}}>0, \tag*{(17)} a k x k k ( − 1 ) k f N ( − x k ) ≥ 1 − 2 1 − r k + 1 x k > 0 , (17) where omitting the last term only improves the estimate when k = N k=N k = N f N ( 0 ) > 0 f_N(0)>0 f N ( 0 ) > 0 N N N
( − x k , − x k − 1 ) ( 1 ≤ k ≤ N ) . (-x_k,-x_{k-1})\qquad(1\leq k\leq N). ( − x k , − x k − 1 ) ( 1 ≤ k ≤ N ) . The degree is N N N a r , … , a s a_r,\ldots,a_s a r , … , a s f r , s f_{r,s} f r , s
The estimate (17) also holds with f f f f N f_N f N N → ∞ N\to\infty N → ∞ f f f f ( 0 ) = a 0 > 0 f(0)=a_0>0 f ( 0 ) = a 0 > 0 f f f f N f_N f N N N N x k → ∞ x_k \to\infty x k → ∞ f ( − x k ) ≠ 0 f(-x_k) \ne0 f ( − x k ) = 0 f f f
The entire functions in Theorem A are locally uniform limits of polynomials with positive coefficients and negative real zeros. They therefore belong to the Laguerre–Pólya class of type I and are section-hyperbolic in the terminology of [27 ] .
Main construction
Proof of Theorem A. Set a 0 = a 1 = 1 a_0=a_1=1 a 0 = a 1 = 1 n ≥ 2 n \ge2 n ≥ 2 a 0 , … , a n − 1 a_0,\ldots,a_{n-1} a 0 , … , a n − 1 0 ≤ r < n 0 \le r<n 0 ≤ r < n
g r , n ( X ) = ∑ j = r n − 1 a j X n − j . (18) g_{r,n}(X)=\sum_{j=r}^{n-1}a_jX^{n-j}. \tag*{(18)} g r , n ( X ) = j = r ∑ n − 1 a j X n − j . (18) Thus g 0 , n = g n g_{0,n}=g_n g 0 , n = g n a n = t a_n=t a n = t
X n − r f r , n ( 1 / X ) = g r , n ( X ) + t , g r , n + 1 ( X ) = X g r , n ( X ) + t X . (19) X^{n-r}f_{r,n}(1/X)=g_{r,n}(X)+t,\qquad g_{r,n+1}(X)=Xg_{r,n}(X)+tX. \tag*{(19)} X n − r f r , n ( 1/ X ) = g r , n ( X ) + t , g r , n + 1 ( X ) = X g r , n ( X ) + tX . (19) We maintain the following condition: the polynomials g r , n g_{r,n} g r , n 0 ≤ r ≤ n − 2 0 \le r \le n-2 0 ≤ r ≤ n − 2 n = 2 n=2 n = 2 g 0 , 2 = X 2 + X g_{0,2}=X^2+X g 0 , 2 = X 2 + X
Let E E E K r , s K_{r,s} K r , s s < n s<n s < n 0 ≤ r ≤ s − 2 0 \le r \le s-2 0 ≤ r ≤ s − 2 E = Q E=\mathbb{Q} E = Q n = 2 n=2 n = 2
η n = min { ε n , 2 − n 2 , a n − 1 2 4 a n − 2 } > 0. (20) \eta_n=\min\left\{\varepsilon_n,2^{-n^2},\frac{a_{n-1}^2}{4a_{n-2}}\right\}>0. \tag*{(20)} η n = min { ε n , 2 − n 2 , 4 a n − 2 a n − 1 2 } > 0. (20) For 0 ≤ r ≤ n − 1 0 \le r \le n-1 0 ≤ r ≤ n − 1 X g r , n ( X ) Xg_{r,n}(X) X g r , n ( X ) n + 1 , n , … , 2 n+1,n,\ldots,2 n + 1 , n , … , 2 Lemma 2.3 therefore excludes only finitely many values of t t t g r , n + 1 g_{r,n+1} g r , n + 1
∏ r = 0 n − 2 ( g r , n ( X ) + t ) \prod_{r=0}^{n-2}\left(g_{r,n}(X)+t\right) r = 0 ∏ n − 2 ( g r , n ( X ) + t ) has a repeated root. This adds only finitely many values, by the separability assertion in Lemma 2.4 . Call the resulting finite set F n F_n F n a n = t a_n=t a n = t ( 0 , η n ) ∩ Q (0,\eta_n)\cap\mathbb{Q} ( 0 , η n ) ∩ Q F n F_n F n
The symmetric choice. Use this choice when n = 2 n=2 n = 2 n ∈ B n\in B n ∈ B Lemma 2.4 (i), the monic polynomial
P n ( X , U ) = ∏ r = 0 n − 2 g r , n ( X ) + 1 / U a r P_n(X,U)=\prod_{r=0}^{n-2}\frac{g_{r,n}(X)+1/U}{a_r} P n ( X , U ) = r = 0 ∏ n − 2 a r g r , n ( X ) + 1/ U has regular splitting field with group
H n = ∏ r = 0 n − 2 S n − r , H_n=\prod_{r=0}^{n-2}\mathfrak{S}_{n-r}, H n = r = 0 ∏ n − 2 S n − r , in the indicated actions on its factors. Here the substitution T = 1 / U T=1/U T = 1/ U Lemma 2.2 gives arbitrarily large positive integers u u u H n H_n H n E E E u u u 1 / u < η n 1/u<\eta_n 1/ u < η n 1 / u ∉ F n 1/u\notin F_n 1/ u ∈ / F n
a n = 1 u . a_n=\frac{1}{u}. a n = u 1 . The finite set F n F_n F n u u u (19) preserves each splitting field, since a n ≠ 0 a_n \ne0 a n = 0 K r , n K_{r,n} K r , n E E E
The choice with one rational root. Use this choice when n ≥ 3 n \ge3 n ≥ 3 n ∉ B n \notin B n ∈ / B Lemma 2.4 (ii) with g 0 = g 0 , n g_0=g_{0,n} g 0 = g 0 , n g r , n g_{r,n} g r , n R = − 1 / U R=-1/U R = − 1/ U
Q g 0 , n ( X , − 1 / U ) a 0 ∏ r = 1 n − 2 g r , n ( X ) − g 0 , n ( − 1 / U ) a r \frac{Q_{g_{0,n}}(X,-1/U)}{a_0}\prod_{r=1}^{n-2}\frac{g_{r,n}(X)-g_{0,n}(-1/U)}{a_r} a 0 Q g 0 , n ( X , − 1/ U ) r = 1 ∏ n − 2 a r g r , n ( X ) − g 0 , n ( − 1/ U ) is monic and separable and has regular splitting field with group
H n ′ = S n − 1 × ∏ r = 1 n − 2 S n − r . H'_n=\mathfrak{S}_{n-1}\times\prod_{r=1}^{n-2}\mathfrak{S}_{n-r}. H n ′ = S n − 1 × r = 1 ∏ n − 2 S n − r . By Lemma 2.2, for arbitrarily large positive integers u u u E E E
α = − 1 u , a n = − g 0 , n ( α ) . (21) \alpha=-\frac{1}{u},\qquad a_n=-g_{0,n}(\alpha). \tag*{(21)} α = − u 1 , a n = − g 0 , n ( α ) . (21) As u → ∞ u\to\infty u → ∞
− g 0 , n ( − 1 / u ) = a n − 1 u + O ( u − 2 ) > 0 , -g_{0,n}(-1/u)=\frac{a_{n-1}}{u}+O(u^{-2})>0, − g 0 , n ( − 1/ u ) = u a n − 1 + O ( u − 2 ) > 0 , so 0 < a n < η n 0<a_n<\eta_n 0 < a n < η n u u u − g 0 , n ( − 1 / U ) -g_{0,n}(-1/U) − g 0 , n ( − 1/ U ) a n ∉ F n a_n\notin F_n a n ∈ / F n u u u u u u
We now have
g 0 , n ( X ) + a n = ( X − α ) Q g 0 , n ( X , α ) . (22) g_{0,n}(X)+a_n=(X-\alpha)Q_{g_{0,n}}(X,\alpha). \tag*{(22)} g 0 , n ( X ) + a n = ( X − α ) Q g 0 , n ( X , α ) . (22) The left side is separable. The other factor is irreducible of degree n − 1 n-1 n − 1 S n − 1 \mathfrak{S}_{n-1} S n − 1 H n ′ H'_n H n ′ n − 1 ≥ 2 n-1\ge2 n − 1 ≥ 2 α \alpha α (22) . Reversing the polynomial proves that f n f_n f n − u -u − u n − 1 n-1 n − 1 G n = 1 ⊕ S n − 1 G_n=1\oplus\mathfrak{S}_{n-1} G n = 1 ⊕ S n − 1 Gal ( K r , n / Q ) = S n − r \operatorname{Gal}(K_{r,n}/\mathbb{Q})=\mathfrak{S}_{n-r} Gal ( K r , n / Q ) = S n − r r ≥ 1 r\ge1 r ≥ 1 K r , n K_{r,n} K r , n E E E
In both cases a n ∉ F n a_n\notin F_n a n ∈ / F n g r , n + 1 g_{r,n+1} g r , n + 1 (3) hold by (20) . Lemma 2.6 gives order zero and all the stated assertions about zeros. In particular, all K r , s K_{r,s} K r , s
[ ∏ 2 ≤ s ≤ n 0 ≤ r ≤ s − 2 K r , s : Q ] = ∏ 2 ≤ s ≤ n 0 ≤ r ≤ s − 2 [ K r , s : Q ] . \left[\prod_{\substack{2\le s\le n\\0\le r\le s-2}}K_{r,s}:\mathbb{Q}\right]
=
\prod_{\substack{2\le s\le n\\0\le r\le s-2}}[K_{r,s}:\mathbb{Q}]. 2 ≤ s ≤ n 0 ≤ r ≤ s − 2 ∏ K r , s : Q = 2 ≤ s ≤ n 0 ≤ r ≤ s − 2 ∏ [ K r , s : Q ] . Every finite subfamily occurs for some n n n
Effective choices
A rational sequence is computable if an algorithm returns its n n n n n n ( ε n ) (\varepsilon_n) ( ε n ) n , k n,k n , k q n , k q_{n,k} q n , k ∣ q n , k − ε n ∣ ≤ 2 − k |q_{n,k}-\varepsilon_n|\le2^{-k} ∣ q n , k − ε n ∣ ≤ 2 − k
Proposition 2.9. If membership in B B B ε n \varepsilon_n ε n
Proof. First replace each ε n \varepsilon_n ε n q n , k q_{n,k} q n , k ∣ q n , k − ε n ∣ ≤ 2 − k \lvert q_{n,k}-\varepsilon_n\rvert\leq2^{-k} ∣ q n , k − ε n ∣ ≤ 2 − k q n , k > 2 − k q_{n,k}>2^{-k} q n , k > 2 − k ( q n , k − 2 − k ) / 2 (q_{n,k}-2^{-k})/2 ( q n , k − 2 − k ) /2
At a symmetric step, test u = 1 , 2 , … u=1,2,\ldots u = 1 , 2 , … t = 1 / u t=1/u t = 1/ u t = − g 0 , n ( − 1 / u ) t=-g_{0,n}(-1/u) t = − g 0 , n ( − 1/ u ) 0 < t < η n 0<t<\eta_n 0 < t < η n Lemma 2.3 . Let L L L E E E [10 §§3.6.2 and 4.2] . The degrees in the resulting tower compute [ E L : E ] [EL:E] [ E L : E ]
[ E L : E ] = { ∏ d = 2 n d ! , n = 2 or n ∈ B , ( n − 1 ) ! ∏ d = 2 n − 1 d ! , n ≥ 3 , n ∉ B . [EL:E]=
\begin{cases}
\prod_{d=2}^{n}d!, & n=2\text{ or }n\in B,\\
(n-1)!\prod_{d=2}^{n-1}d!, & n\geq3,\ n\notin B.
\end{cases} [ E L : E ] = { ∏ d = 2 n d ! , ( n − 1 )! ∏ d = 2 n − 1 d ! , n = 2 or n ∈ B , n ≥ 3 , n ∈ / B . The right side is the largest possible degree, since the group embeds in the corresponding product of symmetric groups. Equality therefore gives the full product group and linear disjointness from E E E
Choose the first u u u Lemma 2.2 and the preceding proof guarantee that this search terminates. This determines each coefficient exactly and uniformly from a program deciding B B B R , N ≥ 1 R,N\geq1 R , N ≥ 1 ∣ z ∣ ≤ R \lvert z\rvert\leq R ∣ z ∣ ≤ R N N N
∑ n > N 2 − n 2 R n . \sum_{n>N}2^{-n^2}R^n. n > N ∑ 2 − n 2 R n . Once R 2 − ( 2 N + 3 ) ≤ 1 / 2 R2^{-(2N+3)}\leq1/2 R 2 − ( 2 N + 3 ) ≤ 1/2 1 / 2 1/2 1/2 2 ⋅ 2 − ( N + 1 ) 2 R N + 1 2\cdot2^{-(N+1)^2}R^{N+1} 2 ⋅ 2 − ( N + 1 ) 2 R N + 1 □ \square □
The same exact procedure determines the label of any rational polynomial of degree n ≥ 3 n\geq3 n ≥ 3 Q \mathbb{Q} Q n ! n! n ! S S S n ! / 2 n!/2 n ! /2 A A A O O O S n \mathfrak{S}_n S n A n \mathfrak{A}_n A n
Two further choices can be incorporated into the induction.
Likewise, the negative integer root at a prescribed reducible degree may be required to have absolute value larger than any given bound, since the allowed integers u u u
Bounded positive coefficients
We now restrict the coefficients to a fixed finite alphabet. The topology and the uniform product measure give different typical behaviour for the other frequency.
Proposition 2.12. Fix an integer L ≥ 35 L \ge35 L ≥ 35 Ω L = { 1 , … , L } N ≥ 1 \Omega_L = \{1,\ldots,L\}^{\mathbb{N}_{\ge1}} Ω L = { 1 , … , L } N ≥ 1 a ∈ Ω L a \in\Omega_L a ∈ Ω L
f a ( x ) = 1 + ∑ j ≥ 1 a j x j f_a(x) = 1 + \sum_{j \ge1} a_j x^j f a ( x ) = 1 + j ≥ 1 ∑ a j x j Every finite prefix has a computable continuation such that
lim inf N → ∞ o f a ( N ) = 0 , lim sup N → ∞ o f a ( N ) = 1. \liminf_{N \to\infty} o_{f_a}(N) = 0,\qquad\limsup_{N \to\infty} o_{f_a}(N) = 1. N → ∞ lim inf o f a ( N ) = 0 , N → ∞ lim sup o f a ( N ) = 1. The set of all such sequences is a dense G δ G_\delta G δ Ω L \Omega_L Ω L O ( f a ) = 0 O(f_a) = 0 O ( f a ) = 0 f a f_a f a
A cylinder is the set of sequences beginning with a prescribed finite word. It is both open and closed, and these cylinders form a basis of the product topology on Ω L \Omega_L Ω L
Proof of Proposition 2.12. Let I n ( a ) I_n(a) I n ( a ) f a , n f_{a,n} f a , n f a , n f_{a,n} f a , n { 1 , … , L } \{1,\ldots,L\} { 1 , … , L } [3 ] give constants c , K > 0 c,K>0 c , K > 0 L L L
E I n ≤ K n − c ( n ≥ 3 ) . (23) \mathbb{E}I_n \le K n^{-c}\qquad(n \ge3). \tag*{(23)} E I n ≤ K n − c ( n ≥ 3 ) . (23) Here the constant term is always nonzero, and the finitely many degrees below the threshold in those theorems are absorbed into K K K w = ( a 1 , … , a m ) w=(a_1,\ldots,a_m) w = ( a 1 , … , a m ) L − m L^{-m} L − m
E ( o f a ( N ) ∣ w ) ≤ L m E o f a ( N ) ⟶ 0. \mathbb{E}(o_{f_a}(N)\mid w) \le L^m\mathbb{E}o_{f_a}(N) \longrightarrow0. E ( o f a ( N ) ∣ w ) ≤ L m E o f a ( N ) ⟶ 0. Thus, for every ε > 0 \varepsilon>0 ε > 0 o f a ( N ) < ε o_{f_a}(N)<\varepsilon o f a ( N ) < ε
There are also arbitrarily long extensions with o f a ( N ) > 1 − ε o_{f_a}(N)>1-\varepsilon o f a ( N ) > 1 − ε k k k φ ( k ) / k < ε / 3 \varphi(k)/k<\varepsilon/3 φ ( k ) / k < ε /3 a 0 = 1 a_0=1 a 0 = 1 k k k S r S_r S r r ( m o d k ) r\pmod{k} r ( mod k ) M = max r S r M=\max_r S_r M = max r S r T ≥ 0 T\ge0 T ≥ 0 ( L − 1 ) T ≥ max r S r − min r S r (L-1)T\ge\max_r S_r-\min_r S_r ( L − 1 ) T ≥ max r S r − min r S r T T T k k k M + T − S r M+T-S_r M + T − S r r r r [ T , L T ] [T,LT] [ T , L T ] T T T { 1 , … , L } \{1,\ldots,L\} { 1 , … , L } m ′ m' m ′ C = M + T C=M+T C = M + T
k ∣ m ′ + 1 , f a , m ′ ( x ) ≡ C ( 1 + x + ⋯ + x k − 1 ) ( m o d x k − 1 ) . k \mid m'+1,\qquad f_{a,m'}(x)\equiv C(1+x+\cdots+x^{k-1})\pmod{x^k-1}. k ∣ m ′ + 1 , f a , m ′ ( x ) ≡ C ( 1 + x + ⋯ + x k − 1 ) ( mod x k − 1 ) . Continue by appending ones. If n ≥ m ′ n\ge m' n ≥ m ′ gcd ( n + 1 , k ) > 1 \gcd(n+1,k)>1 g cd( n + 1 , k ) > 1 q ∣ gcd ( n + 1 , k ) q\mid\gcd(n+1,k) q ∣ g cd( n + 1 , k ) q q q Φ q \Phi_q Φ q f a , n f_{a,n} f a , n q < k ≤ m ′ + 1 q<k\le m'+1 q < k ≤ m ′ + 1 1 − φ ( k ) / k 1-\varphi(k)/k 1 − φ ( k ) / k N > m ′ N>m' N > m ′
o f a ( N ) ≥ ( N − m ′ ) ( 1 − φ ( k ) / k ) − k N . o_{f_a}(N)\ge\frac{(N-m')(1-\varphi(k)/k)-k}{N}. o f a ( N ) ≥ N ( N − m ′ ) ( 1 − φ ( k ) / k ) − k . This exceeds 1 − ε 1-\varepsilon 1 − ε N N N
Alternate the two extensions with rational ε \varepsilon ε Proposition 2.9 ; the existence argument ensures termination. This gives a computable continuation of every prefix. For integers h ≥ 2 h \ge2 h ≥ 2 M ≥ 1 M \ge1 M ≥ 1
⋃ N ≥ M { a : o f a ( N ) < 1 / h } , ⋃ N ≥ M { a : o f a ( N ) > 1 − 1 / h } \bigcup_{N \ge M} \{a : o_{f_a}(N) < 1/h\}, \qquad\bigcup_{N \ge M} \{a : o_{f_a}(N) > 1 - 1/h\} N ≥ M ⋃ { a : o f a ( N ) < 1/ h } , N ≥ M ⋃ { a : o f a ( N ) > 1 − 1/ h } are open and dense. Their intersection over h h h M M M G δ G_\delta G δ
On the other hand, (23) gives E ∑ n ≥ 3 I n / n < ∞ \mathbb{E}\sum_{n \ge3} I_n/n < \infty E ∑ n ≥ 3 I n / n < ∞ M < N M < N M < N
1 N ∑ 3 ≤ n ≤ N I n ≤ M N + ∑ n > M I n n . \frac{1}{N}\sum_{3 \le n \le N} I_n \le\frac{M}{N}+\sum_{n>M}\frac{I_n}{n}. N 1 3 ≤ n ≤ N ∑ I n ≤ N M + n > M ∑ n I n . proving O ( f a ) = 0 O(f_a)=0 O ( f a ) = 0 Proposition 3.9 transfers the other-frequency conclusions pointwise to every number field. In particular, the same probability-one set works for all such fields. Finally, 1 ≤ a j ≤ L 1 \le a_j \le L 1 ≤ a j ≤ L
For monic degree-n n n { 1 , … , L } \{1,\ldots,L\} { 1 , … , L } L > e 12 L > e^{12} L > e 12 [6 ] , Corollary 1.2 prove symmetry with probability 1 − O ( 1 / log n ) 1-O(1/\log n) 1 − O ( 1/ log n )
The estimate (23) also gives a computable continuation with zero other frequency. We use conditional expectations to make the choice effective from every prefix.
Proposition 2.13. For fixed L ≥ 35 L \ge35 L ≥ 35 Ω L \Omega_L Ω L O ( f a ) = 0 O(f_a)=0 O ( f a ) = 0
Proof. For the fixed alphabet size L L L c c c K K K (23) . They are fixed parameters of the algorithm; the asserted uniformity is in the prefix. We do not require an effective choice of these constants from L L L
W ( a ) = ∑ n ≥ 3 I n ( a ) n , V ( w ) = E ( W ∣ w ) . W(a)=\sum_{n\ge3}\frac{I_n(a)}{n}, \qquad V(w)=\mathbb{E}(W\mid w). W ( a ) = n ≥ 3 ∑ n I n ( a ) , V ( w ) = E ( W ∣ w ) . For a prefix w w w m m m V ( w ) V(w) V ( w ) w w w N ≥ max { m , 3 } N \ge\max\{m,3\} N ≥ max { m , 3 }
L m K ∑ n > N n − 1 − c ≤ L m K N − c / c . L^m K\sum_{n>N}n^{-1-c}\le L^m K N^{-c}/c. L m K n > N ∑ n − 1 − c ≤ L m K N − c / c . Also V ( w ) = L − 1 ∑ b = 1 L V ( w b ) V(w)=L^{-1}\sum_{b=1}^{L}V(wb) V ( w ) = L − 1 ∑ b = 1 L V ( w b ) 2 − m − 3 2^{-m-3} 2 − m − 3 V ( w ) + 2 − m − 2 V(w)+2^{-m-2} V ( w ) + 2 − m − 2 V ( w ) V(w) V ( w ) W W W V ( w ) V(w) V ( w ) W < ∞ W<\infty W < ∞ O ( f a ) = 0 O(f_a)=0 O ( f a ) = 0
A property is semidecidable under a promise if an algorithm halts exactly on the inputs having the property, among inputs satisfying the promise. Here the inputs are programs for total coefficient sequences. The two uniform continuation procedures turn the halting problem into a frequency-convergence problem within the fixed alphabet.
Corollary 2.14. Under the promise that a program computes coefficients a 0 = 1 a_0=1 a 0 = 1 a j ∈ { 1 , … , L } a_j\in\{1,\ldots,L\} a j ∈ { 1 , … , L } L ≥ 35 L\ge35 L ≥ 35
Proof. Both continuation procedures above are uniform in the prefix. Given a machine, follow a fixed computable maximal-oscillation sequence until it halts; after halting, retain the assigned prefix and use Proposition 2.13 . The other frequency then exists exactly when the machine halts, so nonconvergence is not semidecidable. Conversely, follow a fixed computable zero-frequency sequence until the machine halts, and then use the maximal-oscillation continuation of the assigned prefix. The frequency exists exactly when the machine never halts, so convergence is not semidecidable. At coefficient n n n n n n Proposition 3.9 . □
Local Galois criteria
The arithmetic arguments use two ways to obtain large permutation groups: a single short cycle, or several permutations with two cycles. We first record the group criteria, then explain how local factorizations and ramification determine the group over a number field.
Permutation group criteria
For P ∈ Q [ x ] P \in\mathbb{Q}[x] P ∈ Q [ x ] n n n P ~ ∈ Z [ x ] \widetilde{P} \in\mathbb{Z}[x] P ∈ Z [ x ] ℓ \ell ℓ P ~ \widetilde{P} P P P P ( 2 n − 2 ) (2n-2) ( 2 n − 2 )
A short cycle in a primitive group gives alternating containment. The following form also covers cycles of composite length.
Lemma 3.2. Let G ≤ S n G \le S_n G ≤ S n G G G k k k 2 ≤ k ≤ n / 2 2 \le k \le n/2 2 ≤ k ≤ n /2 G G G A n A_n A n
Proof. The classical Jordan–Marggraff transitivity theorem [29 Theorem A] makes G G G ( n − k + 1 ) (n-k+1) ( n − k + 1 ) ( k + 1 ) (k+1) ( k + 1 ) σ = ( 1 2 ⋯ k ) \sigma=(1\ 2\ \cdots\ k) σ = ( 1 2 ⋯ k ) G G G k k k σ \sigma σ τ = ( 1 2 ⋯ k − 1 k + 1 ) \tau=(1\ 2\ \cdots\ k-1\ k+1) τ = ( 1 2 ⋯ k − 1 k + 1 ) σ τ − 1 = ( 1 k + 1 k ) \sigma\tau^{-1}=(1\ k+1\ k) σ τ − 1 = ( 1 k + 1 k ) G G G A n A_n A n
For the reciprocal families, local ramification gives two cycles whose lengths need not be coprime. Varying these lengths rules out block systems and the exceptional primitive groups.
Lemma 3.3. Let G ≤ S n G \le S_n G ≤ S n n > 64 n>64 n > 64 J \mathcal{J} J
n / 2 < j < n − n ( j ∈ J ) , n/2<j<n-\sqrt{n}\qquad(j\in\mathcal{J}), n /2 < j < n − n ( j ∈ J ) , and that G G G ( j ) ( n − j ) (j)(n-j) ( j ) ( n − j ) j ∈ J j\in\mathcal{J} j ∈ J n = m r n=mr n = m r 2 ≤ m ≤ r 2\le m\le r 2 ≤ m ≤ r j ∈ J j\in\mathcal{J} j ∈ J m m m r r r A n ⊆ G A_n\subseteq G A n ⊆ G
Proof. If a permutation with exactly two point orbits preserves a block partition with block size m m m r r r m ∣ j m\mid j m ∣ j r r r r ∣ j r\mid j r ∣ j m ∣ j m\mid j m ∣ j r ∣ j r\mid j r ∣ j j ∈ J j\in\mathcal{J} j ∈ J m , r m,r m , r G G G
Suppose now that G G G A n A_n A n [32 Theorem 3.3] to an element with shorter cycle length k = n − j k=n-j k = n − j k = 1 k=1 k = 1 k = 4 k=4 k = 4 k = p k=p k = p n = p e n=p^e n = p e e ≥ 2 e\ge2 e ≥ 2 n < k < n / 2 \sqrt{n}<k<n/2 n < k < n /2 k = 1 k=1 k = 1 k = n / 2 k=n/2 k = n /2 n = r 2 n=r^2 n = r 2 r r r r ∣ j r \mid j r ∣ j j ∈ J j \in\mathcal{J} j ∈ J n = r ⋅ r n = r \cdot r n = r ⋅ r G G G A n \mathcal{A}_n A n
We next express alternating containment by irreducibility and one modular factorization. The witness prime and the prime factor degree play different roles.
Definition 3.4. For P ∈ Q [ x ] P \in\mathbb{Q}[x] P ∈ Q [ x ] n ≥ 8 n \ge8 n ≥ 8 C ( P ) = 1 C(P) = 1 C ( P ) = 1
(i) P P P Q \mathbb{Q} Q
(ii) for some good prime ℓ \ell ℓ P ~ \widetilde{P} P p p p n / 2 < p ≤ n − 3 n/2 < p \le n - 3 n /2 < p ≤ n − 3
Otherwise put C ( P ) = 0 C(P) = 0 C ( P ) = 0 ℓ \ell ℓ
This criterion is exact: allowing the witness prime to vary loses no group containing A n \mathcal{A}_n A n
Proposition 3.5. If P ∈ Q [ x ] P \in\mathbb{Q}[x] P ∈ Q [ x ] n ≥ 8 n \ge8 n ≥ 8
C ( P ) = 1 ⟺ Gal ( P / Q ) ⊇ A n . C(P) = 1 \qquad\Longleftrightarrow\qquad\operatorname{Gal}(P/\mathbb{Q}) \supseteq\mathcal{A}_n. C ( P ) = 1 ⟺ Gal ( P / Q ) ⊇ A n . In particular, the definition is independent of the normalization.
Proof. A factor of degree p p p p p p n − p < p n-p < p n − p < p p p p
Suppose a nontrivial block system has block size b b b 1 < b ≤ n / 2 1 < b \le n/2 1 < b ≤ n /2 p p p b < p b < p b < p b b b n n n p p p p < n < 2 p p < n < 2p p < n < 2 p A n \mathcal{A}_n A n [25 Theorem 1.1] .
Conversely, for n > 50 n > 50 n > 50 n / 2 < p < 3 n / 5 ≤ n − 3 n/2 < p < 3n/5 \le n - 3 n /2 < p < 3 n /5 ≤ n − 3 [33 ] . For 8 ≤ n ≤ 50 8 \le n \le50 8 ≤ n ≤ 50 n / 2 < p ≤ n − 3 n/2 < p \le n - 3 n /2 < p ≤ n − 3 [ p + 3 , 2 p − 1 ] [p + 3, 2p - 1] [ p + 3 , 2 p − 1 ] [ 8 , 57 ] [8, 57] [ 8 , 57 ] p p p A n \mathcal{A}_n A n p p p ( p , 1 , … , 1 ) (p,1,\ldots,1) ( p , 1 , … , 1 ) [44 ] . Containment also gives transitivity, hence irreducibility.
Rational irreducibility cannot be replaced by irreducibility modulo some prime. When n n n A n \mathcal{A}_n A n n n n A n \mathcal{A}_n A n ℓ \ell ℓ
Newton polygons and change of base field
We use valuations with value group Z \mathbb{Z} Z p p p F F F p p p v ( p ) = 1 v(p) = 1 v ( p ) = 1 Proposition 3.5 without a modular factorization.
Lemma 3.7. Let P ∈ F [ X ] P \in F[X] P ∈ F [ X ] n n n F F F P P P p p p n / 2 < p ≤ n − 3 n/2 < p \le n - 3 n /2 < p ≤ n − 3 Gal F ( P ) ⊇ A n \operatorname{Gal}_F(P) \supseteq\mathcal{A}_n Gal F ( P ) ⊇ A n
Proof. A root valuation with denominator p p p p p p p p p p p p p p p 2 p > n 2p > n 2 p > n Proposition 3.5 , and Jordan’s theorem give the conclusion. This is the usual Newton-polygon criterion; compare [21 Theorem 2.2] .
Two local factorizations can also prove global irreducibility if their possible proper factor degrees are disjoint.
Lemma 3.8. Let P ∈ F [ X ] P \in F[X] P ∈ F [ X ] n n n
( 0 , 0 ) , ( j i , − 1 ) , ( n , 0 ) ( i = 1 , 2 ) , n / 2 ≤ j 1 < j 2 < n . (0,0),\ (j_i,-1),\ (n,0) \qquad(i=1,2), \qquad n/2 \le j_1 < j_2 < n. ( 0 , 0 ) , ( j i , − 1 ) , ( n , 0 ) ( i = 1 , 2 ) , n /2 ≤ j 1 < j 2 < n . Then P P P F F F ( 0 , 0 ) (0,0) ( 0 , 0 ) ( n , − 1 ) (n,-1) ( n , − 1 )
Proof. At the i i i j i j_i j i n − j i n-j_i n − j i F F F { j 1 , n − j 1 } \{j_1,n-j_1\} { j 1 , n − j 1 } { j 2 , n − j 2 } \{j_2,n-j_2\} { j 2 , n − j 2 }
Once the degree exceeds that of a fixed base field, alternating containment is unchanged by extending scalars.
Proposition 3.9. Let F / Q F/\mathbb{Q} F / Q P ∈ Q [ X ] P \in\mathbb{Q}[X] P ∈ Q [ X ] n ≥ 5 n \ge5 n ≥ 5 n > [ F : Q ] n > [F:\mathbb{Q}] n > [ F : Q ]
Gal F ( P ) ⊇ A n ⟺ Gal Q ( P ) ⊇ A n . \operatorname{Gal}_{F}(P) \supseteq\mathcal{A}_n \Longleftrightarrow\operatorname{Gal}_{\mathbb{Q}}(P) \supseteq\mathcal{A}_n. Gal F ( P ) ⊇ A n ⟺ Gal Q ( P ) ⊇ A n . Consequently, for every series with nonzero rational coefficients, the other-degree labels over F F F Q \mathbb{Q} Q O F ( f ) O_F(f) O F ( f ) O ( f ) O(f) O ( f )
Proof. Let L / Q L/\mathbb{Q} L / Q P P P G = Gal ( L / Q ) G=\operatorname{Gal}(L/\mathbb{Q}) G = Gal ( L / Q ) H = Gal ( L F / F ) H=\operatorname{Gal}(LF/F) H = Gal ( L F / F ) Gal ( L / ( L ∩ F ) ) ≤ G \operatorname{Gal}(L/(L\cap F)) \le G Gal ( L / ( L ∩ F )) ≤ G m = [ G : H ] = [ L ∩ F : Q ] ≤ [ F : Q ] < n m=[G:H]=[L\cap F:\mathbb{Q}] \le[F:\mathbb{Q}]<n m = [ G : H ] = [ L ∩ F : Q ] ≤ [ F : Q ] < n G G G A n \mathcal{A}_n A n G / H G/H G / H A n \mathcal{A}_n A n A n \mathcal{A}_n A n A n \mathcal{A}_n A n A n \mathcal{A}_n A n S m \mathcal{S}_m S m n ! / 2 > m ! n!/2>m! n ! /2 > m ! A n \mathcal{A}_n A n H H H H ≤ G H\le G H ≤ G A n \mathcal{A}_n A n
For small degrees, an unramified prime provides another way to control the change of base field. Odd inertia is particularly useful because it cannot lie in a proper normal subgroup of S n \mathcal{S}_n S n
Lemma 3.10. Let L / Q L/\mathbb{Q} L / Q F F F p p p F ~ \widetilde{F} F E = L ∩ F ~ E=L\cap\widetilde{F} E = L ∩ F
(i) If Gal ( L / Q ) = S n \operatorname{Gal}(L/\mathbb{Q})=\mathcal{S}_n Gal ( L / Q ) = S n n ≥ 2 n\ge2 n ≥ 2 p p p E = Q E=\mathbb{Q} E = Q
(ii) If n ≥ 5 n\ge5 n ≥ 5 A n ⊆ Gal ( L / Q ) ≤ S n \mathcal{A}_n\subseteq\operatorname{Gal}(L/\mathbb{Q})\le\mathcal{S}_n A n ⊆ Gal ( L / Q ) ≤ S n p p p A n ⊆ Gal ( L / E ) \mathcal{A}_n\subseteq\operatorname{Gal}(L/E) A n ⊆ Gal ( L / E )
Proof. Every conjugate of F F F p p p Q p \mathbb{Q}_p Q p F ~ \widetilde{F} F E E E p p p Gal ( L / E ) \operatorname{Gal}(L/E) Gal ( L / E ) p p p S n \mathcal{S}_n S n A n \mathcal{A}_n A n n = 2 , 3 , 4 n=2,3,4 n = 2 , 3 , 4 n ≥ 5 n\ge5 n ≥ 5 A n \mathcal{A}_n A n S n \mathcal{S}_n S n A n \mathcal{A}_n A n
Reciprocal coefficients and binomial sections
The proof of Theorem B has two parts. We choose primes at which exactly one coefficient has valuation − 1 -1 − 1
Throughout this section, s = a / b ∈ Q ∖ Z s=a/b\in\mathbb{Q}\setminus\mathbb{Z} s = a / b ∈ Q ∖ Z b ≥ 2 b\ge2 b ≥ 2 C ≥ 0 C\ge0 C ≥ 0 F F F rad ( b ) \operatorname{rad}(b) rad ( b ) b b b
M = b rad ( b ) , Q = lcm ( M , 6 ) , H = max { 3 , ∣ a ∣ , b , C + 1 , R F } , (24) M=b\operatorname{rad}(b),\qquad Q=\operatorname{lcm}(M,6),\qquad H=\max\{3,\lvert a\rvert,b,C+1,R_F\}, \tag*{(24)} M = b rad ( b ) , Q = lcm ( M , 6 ) , H = max { 3 , ∣ a ∣ , b , C + 1 , R F } , (24) N ( a , b , C , F ) = ⌈ max { exp ( max { 60 , Q } ) , 100 H } ⌉ . (25) N(a,b,C,F)=\left\lceil\max\{\exp(\max\{60,Q\}),100H\}\right\rceil. \tag*{(25)} N ( a , b , C , F ) = ⌈ max { exp ( max { 60 , Q }) , 100 H } ⌉ . (25) All logarithms are natural. These bounds are chosen to make the prime selection fully explicit; the half-integral cases admit the sharper thresholds stated in the introduction.
Primes avoiding two divisors
Set
c = { 2 , a , b odd , 1 , otherwise . c=\begin{cases}
2,&a,b\text{ odd},\\
1,&\text{otherwise}.
\end{cases} c = { 2 , 1 , a , b odd , otherwise . Then ( c , a b ) = 1 (c,ab)=1 ( c , ab ) = 1 c < b c<b c < b b / c ≥ 3 / 2 b/c\ge3/2 b / c ≥ 3/2 ρ ( m o d Q ) \rho\pmod Q ρ ( mod Q )
c ρ ≡ a + b ( m o d M ) . (26) c\rho\equiv a+b\pmod M. \tag*{(26)} c ρ ≡ a + b ( mod M ) . (26) If 2 ∤ M 2\nmid M 2 ∤ M ρ ≡ 1 ( m o d 2 ) \rho\equiv1\pmod2 ρ ≡ 1 ( mod 2 ) 3 ∤ M 3\nmid M 3 ∤ M ρ ( m o d 3 ) \rho\pmod3 ρ ( mod 3 ) { 1 , 2 } \{1,2\} { 1 , 2 } c ρ − a ≢ 0 ( m o d 3 ) c\rho-a\not\equiv0\pmod3 c ρ − a ≡ 0 ( mod 3 ) ( ρ , Q ) = 1 (\rho,Q)=1 ( ρ , Q ) = 1 p ≡ ρ ( m o d Q ) p\equiv\rho\pmod Q p ≡ ρ ( mod Q )
j = c p − a b j=\frac{cp-a}{b} j = b c p − a is 1 1 1 rad ( b ) \operatorname{rad}(b) rad ( b ) 6 6 6 3 ∤ j 3\nmid j 3 ∤ j b b b (26) makes j j j b b b a a a c = 1 c=1 c = 1 a a a c = 2 c=2 c = 2 c p − a cp-a c p − a
The next estimate supplies the cycle lengths required by Lemma 3.3 . The surplus of primes will also allow us to discard a bounded number of primes excluded by polynomial weights.
Lemma 4.2. Suppose n ≥ N ( a , b , C , F ) n\ge N(a,b,C,F) n ≥ N ( a , b , C , F )
κ = b 8 c , U = 6 κ n , V = 7 κ n , W = V − U = κ n , L = log n . \kappa=\frac{b}{8c},\qquad U=6\kappa n,\qquad V=7\kappa n,\qquad W=V-U=\kappa n,\qquad L=\log n. κ = 8 c b , U = 6 κn , V = 7 κn , W = V − U = κn , L = log n . Let
P = { p prime : U < p ≤ V , p ≡ ρ ( m o d Q ) } . \mathcal{P}=\{p\text{ prime}:U<p\le V,\ p\equiv\rho\pmod Q\}. P = { p prime : U < p ≤ V , p ≡ ρ ( mod Q )} . Then
∣ P ∣ > 4 W 5 φ ( Q ) L > n . (27) \lvert\mathcal{P}\rvert>\frac{4W}{5\varphi(Q)L}>\sqrt{n}. \tag*{(27)} ∣ P ∣ > 5 φ ( Q ) L 4 W > n . (27) For every factorization n = m r n=mr n = m r 2 ≤ m ≤ r 2\le m\le r 2 ≤ m ≤ r
W 10 φ ( Q ) L > n (28) \frac{W}{10\varphi(Q)L}>\sqrt{n} \tag*{(28)} 10 φ ( Q ) L W > n (28) primes in P \mathcal{P} P
m ∤ c p − a b and r ∤ c p − a b . m\nmid\frac{cp-a}{b}\qquad\text{and}\qquad r\nmid\frac{cp-a}{b}. m ∤ b c p − a and r ∤ b c p − a . Every prime in P \mathcal{P} P n + C n+C n + C R F R_F R F
7 n 10 < j < 9 n 10 , n < n − j < n 2 . \frac{7n}{10}<j<\frac{9n}{10},\qquad\sqrt{n}<n-j<\frac{n}{2}. 10 7 n < j < 10 9 n , n < n − j < 2 n . The proof is given in Appendix § 8 , where all constants are made explicit.
The local discriminant
One coefficient of valuation − 1 -1 − 1 z ∈ Q p × z \in\mathbb{Q}_p^\times z ∈ Q p × [ z ] p [z]_p [ z ] p Q p × / Q p × 2 \mathbb{Q}_p^\times/\mathbb{Q}_p^{\times2} Q p × / Q p × 2
Lemma 4.4. Let p > n p>n p > n P ( x ) = ∑ i = 0 n d i x i ∈ Q p [ x ] P(x)=\sum_{i=0}^n d_i x^i \in\mathbb{Q}_p[x] P ( x ) = ∑ i = 0 n d i x i ∈ Q p [ x ]
v p ( d 0 ) = v p ( d n ) = 0 , v p ( d j ) = − 1 ( 0 < j < n ) , v_p(d_0)=v_p(d_n)=0,\qquad v_p(d_j)=-1\quad(0<j<n), v p ( d 0 ) = v p ( d n ) = 0 , v p ( d j ) = − 1 ( 0 < j < n ) , and v p ( d i ) ≥ 0 v_p(d_i)\geq0 v p ( d i ) ≥ 0 i i i k = n − j k=n-j k = n − j P P P Q p \mathbb{Q}_p Q p j , k j,k j , k
v p ( Disc P ) = − n . (29) v_p(\operatorname{Disc} P)=-n. \tag*{(29)} v p ( Disc P ) = − n . (29) If j , k j,k j , k
[ Disc P ] p = [ ( − 1 ) n / 2 − 1 j k ] p . (30) [\operatorname{Disc} P]_p=[(-1)^{n/2-1}jk]_p. \tag*{(30)} [ Disc P ] p = [( − 1 ) n /2 − 1 j k ] p . (30) Proof. The Newton polygon has vertices ( 0 , 0 ) , ( j , − 1 ) , ( n , 0 ) (0,0),(j,-1),(n,0) ( 0 , 0 ) , ( j , − 1 ) , ( n , 0 ) j j j 1 / j 1/j 1/ j A A A p Z p p\mathbb{Z}_p p Z p v p ( A ( 0 ) ) = 1 v_p(A(0))=1 v p ( A ( 0 )) = 1 − 1 / k -1/k − 1/ k B B B E ( x ) = x k B ( 1 / x ) / B ( 0 ) E(x)=x^kB(1/x)/B(0) E ( x ) = x k B ( 1/ x ) / B ( 0 ) k k k j , k < p j,k<p j , k < p
For a monic Eisenstein polynomial H H H e < p e<p e < p α \alpha α
H ′ ( α ) = e α e − 1 ( 1 + η ) , v p ( η ) > 0. H'(\alpha)=e\alpha^{e-1}(1+\eta),\qquad v_p(\eta)>0. H ′ ( α ) = e α e − 1 ( 1 + η ) , v p ( η ) > 0. Indeed, the leading derivative term has valuation ( e − 1 ) / e (e-1)/e ( e − 1 ) / e K = Q p ( α ) K=\mathbb{Q}_p(\alpha) K = Q p ( α )
Disc H = ( − 1 ) e ( e − 1 ) / 2 e e N K / Q p ( α ) e − 1 N K / Q p ( 1 + η ) . \operatorname{Disc} H=(-1)^{e(e-1)/2}e^eN_{K/\mathbb{Q}_p}(\alpha)^{e-1}N_{K/\mathbb{Q}_p}(1+\eta). Disc H = ( − 1 ) e ( e − 1 ) /2 e e N K / Q p ( α ) e − 1 N K / Q p ( 1 + η ) . Thus v p ( Disc H ) = e − 1 v_p(\operatorname{Disc} H)=e-1 v p ( Disc H ) = e − 1 e e e
[ Disc H ] p = [ ( − 1 ) ( e − 1 ) / 2 e ] p . (31) [\operatorname{Disc} H]_p=[(-1)^{(e-1)/2}e]_p. \tag*{(31)} [ Disc H ] p = [( − 1 ) ( e − 1 ) /2 e ] p . (31) The norm of 1 + η 1+\eta 1 + η α \alpha α
Reversal gives Disc B = Disc E / E ( 0 ) 2 k − 2 \operatorname{Disc} B=\operatorname{Disc} E/E(0)^{2k-2} Disc B = Disc E / E ( 0 ) 2 k − 2 v p ( Disc B ) = − ( k − 1 ) v_p(\operatorname{Disc} B)=-(k-1) v p ( Disc B ) = − ( k − 1 ) A A A B B B − 1 / k -1/k − 1/ k v p ( Res ( A , B ) ) = − j v_p(\operatorname{Res}(A,B))=-j v p ( Res ( A , B )) = − j P P P
v p ( Disc P ) = ( j − 1 ) − ( k − 1 ) − 2 j = − n . v_p(\operatorname{Disc} P)=(j-1)-(k-1)-2j=-n. v p ( Disc P ) = ( j − 1 ) − ( k − 1 ) − 2 j = − n . For square classes the leading-coefficient factor, the resultant squared, and the reversal factor are all squares. Applying (31) to A , E A,E A , E (30) . □
Alternating containment
Consider the polynomials R n R_n R n p ∈ P p\in\mathcal{P} p ∈ P Lemma 4.2 , the unique denominator divisible by p p p a + b j = c p a+bj=cp a + bj = c p Lemma 4.4 therefore gives local factors of degrees j , n − j j,n-j j , n − j p > R F p>R_F p > R F F F F p p p v ( p ) = 1 v(p)=1 v ( p ) = 1
Two distinct primes of P \mathcal{P} P j 1 , j 2 > n / 2 j_1,j_2>n/2 j 1 , j 2 > n /2 Lemma 3.8 proves irreducibility over F F F ( j ) ( n − j ) (j)(n-j) ( j ) ( n − j ) p ∈ P p\in\mathcal{P} p ∈ P Lemma 4.2 verifies all the hypotheses of Lemma 3.3 , which gives alternating containment. If n n n ( − 1 ) n − 2 = − 1 (-1)^{n-2}=-1 ( − 1 ) n − 2 = − 1 S n \mathfrak{S}_n S n
Counting the even exceptions
For even n n n j j j n − j n-j n − j M M M j ≡ 1 ( m o d rad ( b ) ) j \equiv1 \pmod{\operatorname{rad}(b)} j ≡ 1 ( mod rad ( b )) b b b c c c b b b
D n = ( − 1 ) n / 2 a ( a + b n ) . (32) D_n = (-1)^{n/2}a(a+bn). \tag*{(32)} D n = ( − 1 ) n /2 a ( a + bn ) . (32) Since j ≡ − a / b j \equiv-a/b j ≡ − a / b n − j ≡ ( a + b n ) / b ( m o d p ) n-j \equiv(a+bn)/b \pmod p n − j ≡ ( a + bn ) / b ( mod p ) Lemma 4.4 shows that
[ Disc R n ] p = [ D n ] p . (33) [\operatorname{Disc} R_n]_p = [D_n]_p. \tag*{(33)} [ Disc R n ] p = [ D n ] p . (33) Here p > ∣ a ∣ p>|a| p > ∣ a ∣ p ∤ b p\nmid b p ∤ b p ∣ D n p\mid D_n p ∣ D n n − j < p n-j<p n − j < p p p p Disc R n \operatorname{Disc} R_n Disc R n j , n j,n j , n
Let
W F = ( F × 2 ∩ Q × ) / Q × 2 . W_F = (F^{\times2}\cap\mathbb{Q}^{\times})/\mathbb{Q}^{\times2}. W F = ( F × 2 ∩ Q × ) / Q × 2 . This is finite, since its nontrivial elements correspond to quadratic subfields of F F F δ \delta δ Disc R n \operatorname{Disc} R_n Disc R n F F F δ \delta δ
( δ D n p ) = 1 (34) \left(\frac{\delta D_n}{p}\right)=1 \tag*{(34)} ( p δ D n ) = 1 (34) at every prime in the prescribed interval and progression, once n n n a , b , C , F a,b,C,F a , b , C , F M M M 3 ∤ j 3\nmid j 3 ∤ j
Fix Y Y Y n n n Y ≤ n ≤ 9 Y / 8 Y\le n\le9Y/8 Y ≤ n ≤ 9 Y /8 c c c
P Y = { p : 27 b Y 32 c < p < 7 b Y 8 c , p ≡ ( a + b ) c − 1 ( m o d M ) } \mathcal{P}_Y=\left\{p:\frac{27bY}{32c}<p<\frac{7bY}{8c},\quad p\equiv(a+b)c^{-1}\pmod M\right\} P Y = { p : 32 c 27 bY < p < 8 c 7 bY , p ≡ ( a + b ) c − 1 ( mod M ) } lies in the permitted interval for every such n n n P Y ≍ a , b Y / log Y \mathcal{P}_Y\asymp_{a,b}Y/\log Y P Y ≍ a , b Y / log Y [28 ] . For fixed δ \delta δ n n n δ \delta δ d n d_n d n δ D n \delta D_n δ D n d n ≠ 1 d_n\ne1 d n = 1
Δ ( d n ) = { d n , d n ≡ 1 ( m o d 4 ) , 4 d n , d n ≢ 1 ( m o d 4 ) . \Delta(d_n)=
\begin{cases}
d_n, & d_n\equiv1\pmod4,\\
4d_n, & d_n\not\equiv1\pmod4.
\end{cases} Δ ( d n ) = { d n , 4 d n , d n ≡ 1 ( mod 4 ) , d n ≡ 1 ( mod 4 ) . The primitive quadratic character χ d n ( m ) = ( Δ ( d n ) / m ) \chi_{d_n}(m)=(\Delta(d_n)/m) χ d n ( m ) = ( Δ ( d n ) / m ) ∣ Δ ( d n ) ∣ ≪ a , b , F Y |\Delta(d_n)|\ll_{a,b,F}Y ∣Δ ( d n ) ∣ ≪ a , b , F Y d n d_n d n (34) says that
∑ p ∈ P Y χ d n ( p ) = P Y . \sum_{p\in\mathcal{P}_Y}\chi_{d_n}(p)=\mathcal{P}_Y. p ∈ P Y ∑ χ d n ( p ) = P Y . Heath–Brown’s quadratic large sieve [22 Corollary 1] states that, for positive integers Q 0 , Z Q_0,Z Q 0 , Z z m z_m z m
∑ χ r e a l p r i m i t i v e cond ( χ ) ≤ Q 0 ∣ ∑ m ≤ Z z m χ ( m ) ∣ 2 ≪ η ( Q 0 Z ) η ( Q 0 + Z ) ∑ m ≤ Z ∣ z m ∣ 2 ( η > 0 ) . (35) \sum_{\substack{\chi\ \mathrm{real\ primitive}\\ \operatorname{cond}(\chi)\le Q_0}}
\left|\sum_{m\le Z}z_m\chi(m)\right|^2
\ll_{\eta}(Q_0Z)^{\eta}(Q_0+Z)\sum_{m\le Z}|z_m|^2
\qquad(\eta>0). \tag*{(35)} χ real primitive cond ( χ ) ≤ Q 0 ∑ m ≤ Z ∑ z m χ ( m ) 2 ≪ η ( Q 0 Z ) η ( Q 0 + Z ) m ≤ Z ∑ ∣ z m ∣ 2 ( η > 0 ) . (35) Take Q 0 , Z ≍ a , b , F Y Q_0,Z\asymp_{a,b,F}Y Q 0 , Z ≍ a , b , F Y P Y \mathcal{P}_Y P Y z m = 1 m ∈ P Y z_m=\mathbf{1}_{m\in\mathcal{P}_Y} z m = 1 m ∈ P Y P Y 2 \mathcal{P}_Y^2 P Y 2 O a , b , F , η ( Y 2 η log Y ) O_{a,b,F,\eta}(Y^{2\eta}\log Y) O a , b , F , η ( Y 2 η log Y ) d d d
δ ( − 1 ) n / 2 a ( a + b n ) = d t 2 \delta(-1)^{n/2}a(a+bn)=dt^2 δ ( − 1 ) n /2 a ( a + bn ) = d t 2 has O a , b , F ( Y ) O_{a,b,F}(\sqrt{Y}) O a , b , F ( Y ) n n n t ≪ a , b , F Y t\ll_{a,b,F}\sqrt{Y} t ≪ a , b , F Y n n n d = 1 d=1 d = 1 W F W_F W F O a , b , F , η ( Y 1 / 2 + 2 η log Y ) O_{a,b,F,\eta}(Y^{1/2+2\eta}\log Y) O a , b , F , η ( Y 1/2 + 2 η log Y ) η = ε / 4 \eta=\varepsilon/4 η = ε /4 Y ε / 2 Y^{\varepsilon/2} Y ε /2 9 / 8 9/8 9/8
Series and polynomial weights
For a fixed sequence ( u j ) (u_j) ( u j ) u j u_j u j j + C j+C j + C u j = v j / ( j ! ) r u_j=v_j/(j!)^r u j = v j / ( j ! ) r v j v_j v j r ≥ 0 r\geq0 r ≥ 0 u j = 2 − j u_j=2^{-j} u j = 2 − j s > 0 s>0 s > 0 C C C h h h s s s s + h s+h s + h u j u_j u j s u j + h / ( s + h ) su_{j+h}/(s+h) s u j + h / ( s + h )
For clarity, the classical specializations are
H s ( x ) = 2 F 1 ( 1 , s ; s + 1 ; x ) = ∑ j ≥ 0 s s + j x j H_s(x)={}_2F_1(1,s;s+1;x)=\sum_{j\geq0}\frac{s}{s+j}x^j H s ( x ) = 2 F 1 ( 1 , s ; s + 1 ; x ) = j ≥ 0 ∑ s + j s x j 1 F r ( s ; s + 1 , 1 , … , 1 ⏟ r − 1 ; x ) = ∑ j ≥ 0 s ( s + j ) ( j ! ) r x j ( r ≥ 1 ) . {}_1F_r(s;s+1,\underbrace{1,\ldots,1}_{r-1};x)=\sum_{j\geq0}\frac{s}{(s+j)(j!)^r}x^j\qquad(r\geq1). 1 F r ( s ; s + 1 , r − 1 1 , … , 1 ; x ) = j ≥ 0 ∑ ( s + j ) ( j ! ) r s x j ( r ≥ 1 ) . The second line includes Kummer’s function at r = 1 r=1 r = 1 s = 1 / 2 s=1/2 s = 1/2 x x x − x -x − x
arctanh x x , arctan x x , π erf x 2 x = ∑ j ≥ 0 ( − 1 ) j x j j ! ( 2 j + 1 ) . \frac{\operatorname{arctanh}\sqrt{x}}{\sqrt{x}},\qquad
\frac{\arctan\sqrt{x}}{\sqrt{x}},\qquad
\frac{\sqrt{\pi}\operatorname{erf}\sqrt{x}}{2\sqrt{x}}=\sum_{j\geq0}\frac{(-1)^j x^j}{j!(2j+1)}. x arctanh x , x arctan x , 2 x π erf x = j ≥ 0 ∑ j ! ( 2 j + 1 ) ( − 1 ) j x j . The quotients have their removable singularities filled in at zero. The identities use the standard hypergeometric and error-function normalizations [14 §§13.2,16.2,7.6] . All these series have triple ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 )
The local proof allows polynomial weights whose prime divisors need not satisfy the preceding bound.
Corollary 4.8. Let r ≥ 0 r\geq0 r ≥ 0 P ∈ Q [ T ] P\in\mathbb{Q}[T] P ∈ Q [ T ] P ( − s ) ≠ 0 P(-s)\ne0 P ( − s ) = 0 a j ∈ Q × a_j\in\mathbb{Q}^{\times} a j ∈ Q ×
a j = P ( j ) ( s + j ) ( j ! ) r a_j=\frac{P(j)}{(s+j)(j!)^r} a j = ( s + j ) ( j ! ) r P ( j ) for all sufficiently large j j j F F F ∑ a j x j \sum a_jx^j ∑ a j x j A n \mathfrak{A}_n A n n n n S n \mathfrak{S}_n S n n n n S n \mathfrak{S}_n S n O s , P , r , F , ε ( X 1 / 2 + ε ) O_{s,P,r,F,\varepsilon}(X^{1/2+\varepsilon}) O s , P , r , F , ε ( X 1/2 + ε ) X X X § 8 .§ 4 gives an explicit degree threshold in terms of these data. In particular, the frequency triple is ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 )
Proof. Clear the fixed denominators of P P P p > n p>n p > n p p p j = ( c p − a ) / b j=(cp-a)/b j = ( c p − a ) / b P(j)\equiv P(-a/b)\nequiv0\pmod p , so the coefficient at index j j j − 1 -1 − 1 P ( n ) P(n) P ( n ) ∣ P ( n ) ∣ ≪ P n deg P |P(n)|\ll_P n^{\deg P} ∣ P ( n ) ∣ ≪ P n d e g P O P ( 1 ) O_P(1) O P ( 1 ) n n n Lemma 4.2 leaves two local factorizations for irreducibility and a cycle length for each divisor-pair condition in Lemma 3.3 . Thus the same proof gives irreducibility and alternating containment. In the large-sieve step the character sum is at least P Y − O P ( 1 ) P_Y-O_P(1) P Y − O P ( 1 ) P Y 2 P_Y^2 P Y 2
The nonzero-coefficient hypothesis permits the finitely many zeros of P ( j ) P(j) P ( j ) P ( T ) = T P(T)=T P ( T ) = T x x x P ( − s ) ≠ 0 P(-s)\ne0 P ( − s ) = 0 P ( T ) = T + s P(T)=T+s P ( T ) = T + s r = 1 r=1 r = 1 e x e^x e x r = 0 r = 0 r = 0 c H s ( x ) + R ( x ) cH_s(x) + R(x) c H s ( x ) + R ( x ) c ∈ Q × c \in\mathbb{Q}^{\times} c ∈ Q × R ∈ Q ( x ) R \in\mathbb{Q}(x) R ∈ Q ( x ) 1 1 1 R R R c s ≠ 0 cs \ne0 cs = 0 − s -s − s
Binomial sections and their exact eventual groups
Define
T n ( y ) = ∑ j = 0 n ( − 1 ) j ( n j ) a a + b j y j , γ n = ( s + 1 ) n n ! . T_n(y) = \sum_{j=0}^{n}(-1)^j\binom{n}{j}\frac{a}{a+bj}y^j,\qquad\gamma_n = \frac{(s+1)_n}{n!}. T n ( y ) = j = 0 ∑ n ( − 1 ) j ( j n ) a + bj a y j , γ n = n ! ( s + 1 ) n . The affine identity
B s , n ( 1 − y ) = γ n T n ( y ) (36) B_{s,n}(1-y) = \gamma_n T_n(y) \tag*{(36)} B s , n ( 1 − y ) = γ n T n ( y ) (36) follows by comparing coefficients, since
∑ i = j n ( s ) i i ! ( i j ) = ( s ) j j ! ( s + j + 1 ) n − j ( n − j ) ! = γ n ( n j ) s s + j . \sum_{i=j}^{n}\frac{(s)_i}{i!}\binom{i}{j} = \frac{(s)_j}{j!}\frac{(s+j+1)_{n-j}}{(n-j)!} = \gamma_n\binom{n}{j}\frac{s}{s+j}. i = j ∑ n i ! ( s ) i ( j i ) = j ! ( s ) j ( n − j )! ( s + j + 1 ) n − j = γ n ( j n ) s + j s . All scalar factors are nonzero. Every prime dividing ( n j ) \binom{n}{j} ( j n ) n n n T n T_n T n F F F
The standard Jacobi formula [14 Equation 18.5.7] , with hypergeometric parameters − n -n − n s s s s + 1 s+1 s + 1 γ n T n ( 1 − x ) \gamma_nT_n(1-x) γ n T n ( 1 − x )
B s , n ( x ) = P n ( s , − n − 1 ) ( 2 x − 1 ) , (37) B_{s,n}(x) = P_n^{(s,-n-1)}(2x-1), \tag*{(37)} B s , n ( x ) = P n ( s , − n − 1 ) ( 2 x − 1 ) , (37) which expresses this family as Jacobi polynomials with one parameter depending on the degree.
To distinguish the two possible groups, write b n = ( s ) n / n ! b_n = (s)_n/n! b n = ( s ) n / n !
( 1 − x ) B s , n ′ ( x ) − s B s , n ( x ) = − ( n + s ) b n x n (1-x)B'_{s,n}(x) - sB_{s,n}(x) = -(n+s)b_nx^n ( 1 − x ) B s , n ′ ( x ) − s B s , n ( x ) = − ( n + s ) b n x n shows separability: a common zero of B s , n , B s , n ′ B_{s,n}, B'_{s,n} B s , n , B s , n ′ B s , n ( 1 ) = ( n + s ) b n / s B_{s,n}(1) = (n+s)b_n/s B s , n ( 1 ) = ( n + s ) b n / s
Disc ( B s , n ) = ( − 1 ) n ( n − 1 ) / 2 s ( n + s ) n − 1 b n n − 2 . (38) \operatorname{Disc}(B_{s,n}) = (-1)^{n(n-1)/2}s(n+s)^{n-1}b_n^{n-2}. \tag*{(38)} Disc ( B s , n ) = ( − 1 ) n ( n − 1 ) /2 s ( n + s ) n − 1 b n n − 2 . (38) For completeness, the product of the derivatives at the roots is s ( n + s ) n − 1 s(n+s)^{n-1} s ( n + s ) n − 1 ( − 1 ) n ( n − 1 ) / 2 b n n − 2 (-1)^{n(n-1)/2}b_n^{n-2} ( − 1 ) n ( n − 1 ) /2 b n n − 2 [18 Lemma 3] .
For even n n n (38) is [ D n ] [D_n] [ D n ] D n D_n D n (32) . The already proved containment therefore gives the classification in Theorem C. The exact exceptional count. Let W F \mathcal{W}_F W F W F W_F W F r ∈ { 0 , 2 } r \in\{0,2\} r ∈ { 0 , 2 } σ r = ( − 1 ) r / 2 \sigma_r = (-1)^{r/2} σ r = ( − 1 ) r /2 δ ∈ W F \delta\in\mathcal{W}_F δ ∈ W F δ σ r a > 0 \delta\sigma_ra > 0 δ σ r a > 0 d δ , r d_{\delta,r} d δ , r δ σ r a \delta\sigma_ra δ σ r a
h δ , r = # { v m o d 4 b : d δ , r v 2 ≡ a + b r ( m o d 4 b ) } . h_{\delta,r} = \#\{v \bmod4b : d_{\delta,r}v^2 \equiv a+br \pmod{4b}\}. h δ , r = # { v mod 4 b : d δ , r v 2 ≡ a + b r ( mod 4 b )} . Then the constant in Theorem C is
c s , F = 1 4 b ∑ r ∈ { 0 , 2 } , δ ∈ W F δ σ r a > 0 h δ , r d δ , r . (39) c_{s,F} = \frac{1}{4\sqrt{b}}\sum_{\substack{r\in\{0,2\},\ \delta\in\mathcal{W}_F\\ \delta\sigma_ra>0}}\frac{h_{\delta,r}}{\sqrt{d_{\delta,r}}}. \tag*{(39)} c s , F = 4 b 1 r ∈ { 0 , 2 } , δ ∈ W F δ σ r a > 0 ∑ d δ , r h δ , r . (39) In particular, it can be computed from the quadratic subfields of F F F
To prove the formula, restrict to n n n a + b n > 0 a+bn > 0 a + bn > 0 n ≡ r ( m o d 4 ) n \equiv r \pmod4 n ≡ r ( mod 4 ) δ D n \delta D_n δ D n δ ∈ W F \delta\in\mathcal{W}_F δ ∈ W F δ σ r a > 0 \delta\sigma_ra > 0 δ σ r a > 0 δ σ r a = d δ , r t 0 2 \delta\sigma_ra = d_{\delta,r}t_0^2 δ σ r a = d δ , r t 0 2
a + b n = d δ , r v 2 ( v ∈ Z > 0 ) . a+bn = d_{\delta,r}v^2 \qquad(v \in\mathbb{Z}_{>0}). a + bn = d δ , r v 2 ( v ∈ Z > 0 ) . Here v v v d δ , r d_{\delta,r} d δ , r a + b n a+bn a + bn h δ , r h_{\delta,r} h δ , r n = ( d δ , r v 2 − a ) / b n=(d_{\delta,r}v^2-a)/b n = ( d δ , r v 2 − a ) / b v v v
h δ , r 4 b b X + a d δ , r + O s , F ( 1 ) = h δ , r 4 b d δ , r X + O s , F ( 1 ) . \frac{h_{\delta,r}}{4b}\sqrt{\frac{bX+a}{d_{\delta,r}}}+O_{s,F}(1)=\frac{h_{\delta,r}}{4\sqrt{bd_{\delta,r}}}\sqrt{X}+O_{s,F}(1). 4 b h δ , r d δ , r b X + a + O s , F ( 1 ) = 4 b d δ , r h δ , r X + O s , F ( 1 ) . Different pairs ( δ , r ) (\delta,r) ( δ , r ) r r r n n n δ \delta δ (8) and (39) . The omitted initial degrees contribute only a constant. Every summand is nonnegative. Thus c s , F = 0 c_{s,F}=0 c s , F = 0 a > 0 a>0 a > 0 a = d t 2 a=dt^2 a = d t 2 ( δ , r ) = ( 1 , 0 ) (\delta,r)=(1,0) ( δ , r ) = ( 1 , 0 ) v = t v=t v = t c s , F > 0 c_{s,F}>0 c s , F > 0
Over Q \mathbb{Q} Q (39) give the following closed formula.
Corollary 4.10. Write ∣ a ∣ = d t 2 |a|=dt^2 ∣ a ∣ = d t 2 d > 0 d>0 d > 0 t ∈ Z > 0 t\in\mathbb{Z}_{>0} t ∈ Z > 0 ω ( b ) \omega(b) ω ( b ) b b b v 2 v_2 v 2
c s , Q = 2 ω ( b ) − 1 b d (40) c_{s,\mathbb{Q}}=\frac{2^{\omega(b)}-1}{\sqrt{bd}} \tag*{(40)} c s , Q = b d 2 ω ( b ) − 1 (40) if a > 0 a>0 a > 0 a < 0 a<0 a < 0 b b b b b b 1 1 1 4 4 4 v 2 ( ∣ a ∣ ) v_2(|a|) v 2 ( ∣ a ∣ ) c s , Q = 0 c_{s,\mathbb{Q}}=0 c s , Q = 0 1 / 2 1/2 1/2 a < 0 a<0 a < 0
Proof. Write ∣ a ∣ = d t 2 |a|=dt^2 ∣ a ∣ = d t 2 d > 0 d>0 d > 0 t ∈ Z > 0 t\in\mathbb{Z}_{>0} t ∈ Z > 0 a > 0 a>0 a > 0 r = 0 r=0 r = 0 d v 2 ≡ a ( m o d 4 b ) dv^2\equiv a\pmod{4b} d v 2 ≡ a ( mod 4 b ) 2 ω ( b ) + 1 2^{\omega(b)+1} 2 ω ( b ) + 1 4 b 4b 4 b b b b b b b v 2 ≡ t 2 ( m o d b ) v^2\equiv t^2\pmod b v 2 ≡ t 2 ( mod b ) 2 ω ( b ) 2^{\omega(b)} 2 ω ( b ) ( t , b ) = 1 (t,b)=1 ( t , b ) = 1 v v v t t t b b b d , t d,t d , t v 2 ≡ t 2 ( m o d 4 b ) v^2\equiv t^2\pmod{4b} v 2 ≡ t 2 ( mod 4 b ) 2 2 2 4 b 4b 4 b (40) .
Suppose a < 0 a<0 a < 0 A = ∣ a ∣ A=|a| A = ∣ a ∣ r = 2 r=2 r = 2
d v 2 ≡ 2 b − A ( m o d 4 b ) . (41) dv^2\equiv2b-A\pmod{4b}. \tag*{(41)} d v 2 ≡ 2 b − A ( mod 4 b ) . (41) If b b b A A A n ≡ 2 ( m o d 4 ) n\equiv2\pmod4 n ≡ 2 ( mod 4 )
D n = A ( b n − A ) ≡ 2 b A − 1 ≡ 3 or 7 ( m o d 8 ) . D_n=A(bn-A)\equiv2bA-1\equiv3\text{ or }7\pmod8. D n = A ( bn − A ) ≡ 2 b A − 1 ≡ 3 or 7 ( mod 8 ) . There is no square. For odd b b b b b b v 2 ≡ − t 2 ( m o d b ) v^2\equiv-t^2\pmod b v 2 ≡ − t 2 ( mod b ) ( t , b ) = 1 (t,b)=1 ( t , b ) = 1 b b b 1 1 1 4 4 4 2 ω ( b ) 2^{\omega(b)} 2 ω ( b ) (41) is soluble exactly when v 2 ( A ) v_2(A) v 2 ( A ) A A A v v v v 2 ( A ) = 1 v_2(A)=1 v 2 ( A ) = 1 v v v v 2 ( A ) > 1 v_2(A)>1 v 2 ( A ) > 1 d v 2 ≡ 2 ( m o d 4 ) dv^2\equiv2\pmod4 d v 2 ≡ 2 ( mod 4 ) d d d v 2 ( A ) v_2(A) v 2 ( A ) 2 ω ( b ) + 1 2^{\omega(b)+1} 2 ω ( b ) + 1 □ \square □
For example, s = − 1 / 2 s=-1/2 s = − 1/2 s = − 1 / 5 s=-1/5 s = − 1/5 X 1 / 2 / 5 + O ( 1 ) X^{1/2}/\sqrt{5}+O(1) X 1/2 / 5 + O ( 1 ) X X X
A numerical upper bound. Put N 0 = N ( a , b , 0 , F ) N_0=N(a,b,0,F) N 0 = N ( a , b , 0 , F ) N 0 = N 2 ( a , 0 , F ) N_0=N_2(a,0,F) N 0 = N 2 ( a , 0 , F ) b = 2 b=2 b = 2 D = ∣ Disc F ∣ D=|\operatorname{Disc}F| D = ∣ Disc F ∣ d = [ F : Q ] d=[F:\mathbb{Q}] d = [ F : Q ] X ≥ 1 X\ge1 X ≥ 1
# { 1 ≤ n ≤ X : Gal F ( B s , n ) ≠ S n } ≤ N 0 − 1 + 2 d ( ⌈ D ∣ a ∣ ( ∣ a ∣ + b X ) ⌉ + 1 ) . (42) \#\{1\le n\le X:\operatorname{Gal}_F(B_{s,n})\ne\mathfrak{S}_n\}\le N_0-1+2d\left(\left\lceil\sqrt{D|a|(|a|+bX)}\right\rceil+1\right). \tag*{(42)} # { 1 ≤ n ≤ X : Gal F ( B s , n ) = S n } ≤ N 0 − 1 + 2 d ( ⌈ D ∣ a ∣ ( ∣ a ∣ + b X ) ⌉ + 1 ) . (42) Indeed, W F W_F W F d d d F F F ∣ W F ∣ \lvert W_F\rvert ∣ W F ∣ ∣ δ ∣ ≤ D \lvert\delta\rvert\le D ∣ δ ∣ ≤ D δ D n \delta D_n δ D n D ∣ a ∣ ( ∣ a ∣ + b X ) D\lvert a\rvert(\lvert a\rvert+bX) D ∣ a ∣ (∣ a ∣ + b X ) N 0 N_0 N 0 (42) .
Central-binomial and half-integral sections
The same local witnesses prove the uniform half-integral criterion and the central-binomial classification. We first record the irreducibility argument.
Proposition 4.12. For every n ≥ 1 n \ge1 n ≥ 1 C n C_n C n H 1 / 2 , n ( x ) = ∑ j = 0 n x j / ( 2 j + 1 ) H_{1/2,n}(x)=\sum_{j=0}^{n}x^j/(2j+1) H 1/2 , n ( x ) = ∑ j = 0 n x j / ( 2 j + 1 ) Q \mathbb{Q} Q
Proof. By (36) , it suffices in the first case to consider T n ( y ) = ∑ j = 0 n ( − 1 ) j ( n j ) y j / ( 2 j + 1 ) T_n(y)=\sum_{j=0}^{n}(-1)^j\binom{n}{j}y^j/(2j+1) T n ( y ) = ∑ j = 0 n ( − 1 ) j ( j n ) y j / ( 2 j + 1 ) n ≥ 5 n \ge5 n ≥ 5 ( n + 1 / 2 , 2 n + 1 ] (n+1/2,2n+1] ( n + 1/2 , 2 n + 1 ] π ( x ) − π ( x / 2 ) ≥ 2 \pi(x)-\pi(x/2)\ge2 π ( x ) − π ( x /2 ) ≥ 2 x ≥ 11 x \ge11 x ≥ 11 [38 Section 2] . For either prime, the only coefficient of valuation − 1 -1 − 1 j = ( p − 1 ) / 2 ∈ [ n / 2 , n ] j=(p-1)/2 \in[n/2,n] j = ( p − 1 ) /2 ∈ [ n /2 , n ] j = n j=n j = n j j j n − j n-j n − j j ∈ [ n / 2 , n ) j \in[n/2,n) j ∈ [ n /2 , n ) n = 1 n=1 n = 1 n = 2 , 3 n=2,3 n = 2 , 3 p = 5 , 7 p=5,7 p = 5 , 7 n = 4 n=4 n = 4 5 , 7 5,7 5 , 7 { 2 } \{2\} { 2 } { 1 , 3 } \{1,3\} { 1 , 3 } H 1 / 2 , n H_{1/2,n} H 1/2 , n
The irreducibility proof is independent of the multipliers. To obtain the uniform containment result, we combine the preceding prime estimates with finite lists of local witnesses.
Proposition 4.13. Let
R n ( x ) = ∑ j = 0 n u n , j 2 j + 1 x j , u n , j ∈ Q × . R_n(x)=\sum_{j=0}^{n}\frac{u_{n,j}}{2j+1}x^j,\qquad u_{n,j}\in\mathbb{Q}^{\times}. R n ( x ) = j = 0 ∑ n 2 j + 1 u n , j x j , u n , j ∈ Q × . where every u n , j u_{n,j} u n , j p > n p>n p > n F F F R n R_n R n n ≥ R F n\ge R_F n ≥ R F A n \mathcal{A}_n A n n ≥ R F n\ge R_F n ≥ R F n ≠ 6 n\ne6 n = 6 n ≥ R F n\ge R_F n ≥ R F S n \mathcal{S}_n S n
Proof of Proposition 4.13. The proof of Proposition 4.12 uses only the valuations at primes p > n p>n p > n n ≥ R F n\ge R_F n ≥ R F F F F F F F n < p < 2 n n<p<2n n < p < 2 n ( j ) ( n − j ) (j)(n-j) ( j ) ( n − j ) j = ( p − 1 ) / 2 j=(p-1)/2 j = ( p − 1 ) /2
For n ≥ max { 10 6 , R F } n\ge\max\{10^6,R_F\} n ≥ max { 1 0 6 , R F } 65 ≤ n < 10 6 65\le n<10^6 65 ≤ n < 1 0 6 Table 1 gives three primes p i = 2 j i + 1 p_i=2j_i+1 p i = 2 j i + 1
Table 1. Three-prime certificates for central-binomial and half-integral reciprocal sections. The indices ( p i − 1 ) / 2 (p_i-1)/2 ( p i − 1 ) /2
n / 2 < j i < n − n . n/2<j_i<n-\sqrt{n}. n /2 < j i < n − n . For every factorization n = m r n=mr n = m r m , r > 1 m,r>1 m , r > 1 m , r m,r m , r j i j_i j i Lemma 3.3 gives alternating containment. To verify a row with degree range [ u , v ] [u,v] [ u , v ] j − , j + j_-,j_+ j − , j +
u > 64 , u > j + , ( u − j + ) 2 > u , v < 2 j − . u>64,\qquad u>j_+,\qquad(u-j_+)^2>u,\qquad v<2j_-. u > 64 , u > j + , ( u − j + ) 2 > u , v < 2 j − . These inequalities persist throughout the interval. The ranges cover every degree from 65 to 1530621. The accompanying verifier checks the endpoints, all primalities by trial division, and the three gcds in each row.
For 5 ≤ n ≤ 64 5\le n\le64 5 ≤ n ≤ 64 { 6 , 10 , 12 , 24 } \{6,10,12,24\} { 6 , 10 , 12 , 24 } Table 2 supplies a prime n + 1 < p ≤ 2 n − 3 n+1<p\le2n-3 n + 1 < p ≤ 2 n − 3 gcd ( n , ( p − 1 ) / 2 ) = 1 \gcd(n,(p-1)/2)=1 g cd( n , ( p − 1 ) /2 ) = 1 j = ( p − 1 ) / 2 j=(p-1)/2 j = ( p − 1 ) /2 j + 2 ≤ n ≤ 2 j − 1 j+2\le n\le2j-1 j + 2 ≤ n ≤ 2 j − 1 gcd ( 11 , 9 ) = gcd ( 22 , 15 ) = gcd ( 23 , 21 ) = 1 \gcd(11,9)=\gcd(22,15)=\gcd(23,21)=1 g cd( 11 , 9 ) = g cd( 22 , 15 ) = g cd( 23 , 21 ) = 1 j j j n − j n-j n − j j > n / 2 j>n/2 j > n /2 j j j n n n 2 ≤ n − j < n / 2 2\le n-j<n/2 2 ≤ n − j < n /2
Table 2. Single-prime certificates in the remaining degrees below 65.
For n = 10 , 12 , 24 n=10,12,24 n = 10 , 12 , 24 2 n − 1 2n-1 2 n − 1 ( n − 1 ) (n-1) ( n − 1 ) [32 Theorem 3.2] leaves only A 10 \mathcal{A}_{10} A 10 S 10 \mathcal{S}_{10} S 10 p + 1 p+1 p + 1 p p p ( 9 ) ( 3 ) , ( 20 ) ( 4 ) (9)(3),(20)(4) ( 9 ) ( 3 ) , ( 20 ) ( 4 ) A n \mathcal{A}_n A n [32 Theorem 3.3] .
Degrees two and three follow from irreducibility. In degree four, inertia at 7 gives a 3-cycle; a transitive subgroup of S 4 \mathcal{S}_4 S 4 A 4 \mathcal{A}_4 A 4 n ≥ 3 n\ge3 n ≥ 3 n < p < 2 n n<p<2n n < p < 2 n S n \mathcal{S}_n S n
In particular, max { 7 , R F } \max\{7,R_F\} max { 7 , R F } v j v_j v j ∣ v j ∣ ≤ B |v_j| \le B ∣ v j ∣ ≤ B r ∈ Z ≥ 0 r \in\mathbb{Z}_{\ge0} r ∈ Z ≥ 0
∑ j ≥ 0 v j ( 2 j + 1 ) ( j ! ) r x j \sum_{j\ge0}\frac{v_j}{(2j+1)(j!)^r}x^j j ≥ 0 ∑ ( 2 j + 1 ) ( j ! ) r v j x j are irreducible and contain A n \mathcal{A}_n A n n ≥ max { 7 , B , R F } n \ge\max\{7,B,R_F\} n ≥ max { 7 , B , R F } S n \mathcal{S}_n S n v j v_j v j j ! j! j ! n n n
We can now determine every central-binomial group. Only degree six requires a local witness beyond the uniform criterion.
Proof of Theorem D. We have C n ( x ) = B 1 / 2 , n ( 4 x ) C_n(x)=B_{1/2,n}(4x) C n ( x ) = B 1/2 , n ( 4 x ) (36) , an affine change of variable and a nonzero scalar multiplication give
T n ( y ) = ∑ j = 0 n ( − 1 ) j ( n j ) 2 j + 1 y j . T_n(y)=\sum_{j=0}^{n}\frac{(-1)^j\binom{n}{j}}{2j+1}y^j. T n ( y ) = j = 0 ∑ n 2 j + 1 ( − 1 ) j ( j n ) y j . Every binomial multiplier is a unit at primes p > n p>n p > n F F F n ≥ R F n\ge R_F n ≥ R F n ≠ 6 n\ne6 n = 6
For degree six, the prime 11 gives a 5-cycle, so irreducibility implies primitivity. We have
C 6 ( x ) ≡ 4 ( x − 1 ) ( x 2 + 3 ) ( x 3 + 4 x 2 + x + 2 ) ( m o d 5 ) . C_6(x)\equiv4(x-1)(x^2+3)(x^3+4x^2+x+2)\pmod5. C 6 ( x ) ≡ 4 ( x − 1 ) ( x 2 + 3 ) ( x 3 + 4 x 2 + x + 2 ) ( mod 5 ) . The quadratic and cubic factors have no roots in F 5 \mathbb{F}_5 F 5 ( 1 , 2 , 3 ) (1,2,3) ( 1 , 2 , 3 ) Q \mathbb{Q} Q S 6 \mathcal{S}_6 S 6 T 6 T_6 T 6 S 6 \mathcal{S}_6 S 6 F F F R F ≤ 6 R_F\le6 R F ≤ 6
In even degree, (38) gives discriminant square class [ ( − 1 ) n / 2 ( 2 n + 1 ) ] [(-1)^{n/2}(2n+1)] [( − 1 ) n /2 ( 2 n + 1 )] (10) . Over Q \mathbb{Q} Q 2 n + 1 = ( 2 r + 1 ) 2 2n+1=(2r+1)^2 2 n + 1 = ( 2 r + 1 ) 2 n = 2 r ( r + 1 ) n=2r(r+1) n = 2 r ( r + 1 ) r ≥ 1 r\ge1 r ≥ 1 n n n (9) .
A monic polynomial irreducible modulo a prime is squarefree there. Dedekind’s theorem therefore forces an n n n n = 2 r ( r + 1 ) n=2r(r+1) n = 2 r ( r + 1 ) A n \mathcal{A}_n A n n n n x n C n ( 1 / x ) x^nC_n(1/x) x n C n ( 1/ x ) S n \mathcal{S}_n S n ( n − 1 ) ! / n ! = 1 / n (n-1)!/n!=1/n ( n − 1 )! / n ! = 1/ n [44 ] . This proves Sun’s assertion [45 part (ii)] . □
The exact number of alternating degrees is
# { 3 ≤ n ≤ X : Gal Q ( C n ) = A n } = ⌊ 2 X + 1 − 1 2 ⌋ = X / 2 + O ( 1 ) ( X ≥ 1 ) . (43) \#\{3\le n\le X:\operatorname{Gal}_{\mathbb{Q}}(C_n)=\mathcal{A}_n\}
=
\left\lfloor\frac{\sqrt{2X+1}-1}{2}\right\rfloor
=
\sqrt{X/2}+O(1)
\qquad(X\ge1). \tag*{(43)} # { 3 ≤ n ≤ X : Gal Q ( C n ) = A n } = ⌊ 2 2 X + 1 − 1 ⌋ = X /2 + O ( 1 ) ( X ≥ 1 ) . (43) Proposition 4.12 also proves the central-binomial case of Sun’s factorial-ratio assertion [46 ] ; the broader assertion remains a separate question.
The excluded degree in the uniform criterion admits only one further group-theoretic possibility.
Remark 4.14. In degree six, the same row hypothesis and R F ≤ 6 R_F\le6 R F ≤ 6 Gal F ( R 6 ) \operatorname{Gal}_F(R_6) Gal F ( R 6 ) S 6 \mathcal{S}_6 S 6 PGL 2 ( 5 ) \operatorname{PGL}_2(5) PGL 2 ( 5 ) [32 ] , Theorem 3.2 leaves precisely these two possibilities. This does not assert that the smaller group occurs for an admissible row.
For the unweighted reciprocal sections, a second finite-field calculation resolves degree six. The real roots also determine the group in degrees congruent to two modulo four.
Corollary 4.15. Put H n ( x ) = ∑ j = 0 n x j / ( 2 j + 1 ) H_n(x)=\sum_{j=0}^{n}x^j/(2j+1) H n ( x ) = ∑ j = 0 n x j / ( 2 j + 1 ) F F F n ≥ R F n\ge R_F n ≥ R F Gal F ( H n ) \operatorname{Gal}_F(H_n) Gal F ( H n ) A n \mathcal{A}_n A n S n \mathcal{S}_n S n n n n Q \mathbb{Q} Q S n \mathcal{S}_n S n 4 ∤ n 4\nmid n 4 ∤ n
Proof. Only degree six remains. Inertia at 11 gives a 5-cycle, so the group over Q \mathbb{Q} Q 13 H 6 13H_6 13 H 6
13 H 6 ( x ) ≡ ( x + 4 ) ( x 2 + 12 x + 8 ) ( x 3 + 13 x 2 + 2 ) ( m o d 17 ) . 13H_6(x) \equiv(x+4)(x^2+12x+8)(x^3+13x^2+2) \pmod{17}. 13 H 6 ( x ) ≡ ( x + 4 ) ( x 2 + 12 x + 8 ) ( x 3 + 13 x 2 + 2 ) ( mod 17 ) . The quadratic and cubic factors have no roots in F 17 \mathbb{F}_{17} F 17 ( 1 , 2 , 3 ) (1,2,3) ( 1 , 2 , 3 ) S 6 S_6 S 6 F F F R F ≤ 6 R_F \le6 R F ≤ 6
For even n n n
H n ( x ) = ∫ 0 1 ∑ j = 0 n ( x t 2 ) j d t > 0 ( x ∈ R ) H_n(x)=\int_0^1\sum_{j=0}^{n}(xt^2)^j\,dt>0\qquad(x\in\mathbb{R}) H n ( x ) = ∫ 0 1 j = 0 ∑ n ( x t 2 ) j d t > 0 ( x ∈ R ) follows from the finite geometric sum: for x < 0 x<0 x < 0 ( 1 − ( x t 2 ) n + 1 ) / ( 1 − x t 2 ) > 0 (1-(xt^2)^{n+1})/(1-xt^2)>0 ( 1 − ( x t 2 ) n + 1 ) / ( 1 − x t 2 ) > 0 x ≥ 0 x\geq0 x ≥ 0 ( − 1 ) n / 2 (-1)^{n/2} ( − 1 ) n /2 n ≡ 2 ( m o d 4 ) n\equiv2\pmod4 n ≡ 2 ( mod 4 )
For comparison, a fixed integral exponent s > 2 s>2 s > 2 A ( ( 1 − x ) − s ) = 0 A((1-x)^{-s})=0 A (( 1 − x ) − s ) = 0 n n n s ( n + s ) s(n+s) s ( n + s ) s ∏ j = 1 s − 1 ( n + j ) / ( s − 1 ) ! s\prod_{j=1}^{s-1}(n+j)/(s-1)! s ∏ j = 1 s − 1 ( n + j ) / ( s − 1 )!
B s , n ( x ) = 1 ( s − 1 ) ! d s − 1 d x s − 1 ∑ j = 0 n + s − 1 x j , B_{s,n}(x)=\frac{1}{(s-1)!}\frac{d^{s-1}}{dx^{s-1}}\sum_{j=0}^{n+s-1}x^j, B s , n ( x ) = ( s − 1 )! 1 d x s − 1 d s − 1 j = 0 ∑ n + s − 1 x j , and [7 Theorem 2] gives irreducibility in density one. Alternating containment in density one is an additional question. The case s = 1 s=1 s = 1 ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) s s s
Catalan sections
Let c j = ( 2 j j ) / ( j + 1 ) c_j=\binom{2j}{j}/(j+1) c j = ( j 2 j ) / ( j + 1 ) j ≥ 0 j\geq0 j ≥ 0
P n ( x ) = ∑ j = 0 n c j x j , Q n ( x ) = x n P n ( 1 / x ) . P_n(x)=\sum_{j=0}^{n}c_jx^j,\qquad Q_n(x)=x^nP_n(1/x). P n ( x ) = j = 0 ∑ n c j x j , Q n ( x ) = x n P n ( 1/ x ) . Seki proved that P n P_n P n Q \mathbb{Q} Q n ≥ 1 n\geq1 n ≥ 1 [41 Theorem 1.1] . To prove Theorem E, we first show that its Galois group is primitive. Local inertia rules out all block systems with at least three blocks. A possible system of two blocks requires a different argument: congruences for the two root sums force their product to have a value incompatible with transitivity. The reduction identities and trace congruences come from Seki’s irreducibility argument [41 Section 4] ; the step here is to apply them to blocks of the Galois action. Once primitivity is established, the same local cycles give the symmetric group and the stated bound over a number field.
Local cycles and discriminants
The polynomial Q n Q_n Q n x n − 1 x^{n-1} x n − 1
∣ α ∣ ≤ max 1 ≤ j ≤ n c j c j − 1 = 4 − 6 n + 1 < 4 (44) |\alpha|\leq\max_{1\leq j\leq n}\frac{c_j}{c_{j-1}}=4-\frac{6}{n+1}<4 \tag*{(44)} ∣ α ∣ ≤ 1 ≤ j ≤ n max c j − 1 c j = 4 − n + 1 6 < 4 (44) by the Eneström–Kakeya bound. Fix a prime n + 1 < p ≤ 2 n n+1<p\leq2n n + 1 < p ≤ 2 n
k = p − 1 2 , d = n − k . k=\frac{p-1}{2},\qquad d=n-k. k = 2 p − 1 , d = n − k . Then 1 ≤ d < n / 2 1 \le d < n/2 1 ≤ d < n /2 p > n + 1 p > n+1 p > n + 1 c j c_j c j v p ( c j ) = 0 v_p(c_j)=0 v p ( c j ) = 0 j ≤ k j \le k j ≤ k v p ( c j ) = 1 v_p(c_j)=1 v p ( c j ) = 1 k < j ≤ n k < j \le n k < j ≤ n Q n Q_n Q n ( 0 , 1 ) (0,1) ( 0 , 1 ) ( d , 0 ) (d,0) ( d , 0 ) p p p
Q ‾ n = x d Q ‾ k , 2 Q ‾ k ( x ) = x k + 1 − ( x − 4 ) k + 1 . (45) \overline{Q}_n=x^d\overline{Q}_k,\qquad2\overline{Q}_k(x)=x^{k+1}-(x-4)^{k+1}. \tag*{(45)} Q n = x d Q k , 2 Q k ( x ) = x k + 1 − ( x − 4 ) k + 1 . (45) The second identity follows by comparing coefficients, using 2 c j ≡ − ( − 4 ) j + 1 ( k + 1 j + 1 ) ( m o d p ) 2c_j\equiv-(-4)^{j+1}\binom{k+1}{j+1}\pmod p 2 c j ≡ − ( − 4 ) j + 1 ( j + 1 k + 1 ) ( mod p )
Q ‾ k ( x ) ( x k + 1 + ( x − 4 ) k + 1 ) = 2 ( x p + x − 4 ) . \overline{Q}_k(x)\left(x^{k+1}+(x-4)^{k+1}\right)=2(x^p+x-4). Q k ( x ) ( x k + 1 + ( x − 4 ) k + 1 ) = 2 ( x p + x − 4 ) . The polynomial on the right has derivative 2 2 2 Q ‾ k \overline{Q}_k Q k
γ p = 4 − γ . (46) \gamma^p=4-\gamma. \tag*{(46)} γ p = 4 − γ . (46) These identities also appear in [41 Section 4.1] .
Hensel’s lemma gives Q n = A p B p Q_n=A_pB_p Q n = A p B p Z p \mathbb{Z}_p Z p A p , B p A_p,B_p A p , B p A ‾ p = x d \overline{A}_p=x^d A p = x d B ‾ p = Q ‾ k \overline{B}_p=\overline{Q}_k B p = Q k B p ( 0 ) B_p(0) B p ( 0 ) v p ( Q n ( 0 ) ) = 1 v_p(Q_n(0))=1 v p ( Q n ( 0 )) = 1 A p A_p A p A p A_p A p d < p d<p d < p B p B_p B p d d d d d d
We also record the discriminant valuation. Each root α \alpha α A p A_p A p 1 / d 1/d 1/ d A p ′ ( α ) A_p'(\alpha) A p ′ ( α ) d α d − 1 d\alpha^{d-1} d α d − 1 ( d − 1 ) / d (d-1)/d ( d − 1 ) / d v p ( Disc ( A p ) ) = d − 1 v_p(\operatorname{Disc}(A_p))=d-1 v p ( Disc ( A p )) = d − 1 B p B_p B p A p , B p A_p,B_p A p , B p
v p ( Disc ( P n ) ) = v p ( Disc ( Q n ) ) = d − 1. (47) v_p(\operatorname{Disc}(P_n))=v_p(\operatorname{Disc}(Q_n))=d-1. \tag*{(47)} v p ( Disc ( P n )) = v p ( Disc ( Q n )) = d − 1. (47) Explicit primes in a short interval
Write I n = ( n + 1 , 4 n / 3 ] I_n=(n+1,4n/3] I n = ( n + 1 , 4 n /3 ] π ( I n ) \pi(I_n) π ( I n ) I n I_n I n
Lemma 5.3. For n ≥ 1000 n\ge1000 n ≥ 1000 I n I_n I n 4 4 4 6 6 6 n ≥ 16384 n\ge16384 n ≥ 16384
π ( I n ) > 2 n 7 log n . (48) \pi(I_n)>\frac{2n}{7\log n}. \tag*{(48)} π ( I n ) > 7 log n 2 n . (48) Proof. Put u = 4 n / 3 u=4n/3 u = 4 n /3 ℓ = n + 1 \ell=n+1 ℓ = n + 1 θ ( x ; q , a ) = ∑ p ≤ x p ≡ a ( m o d q ) log p \theta(x;q,a)=\sum_{\substack{p\le x\\p\equiv a\pmod q}}\log p θ ( x ; q , a ) = ∑ p ≤ x p ≡ a ( mod q ) log p θ ( x ) = θ ( x ; 1 , 1 ) \theta(x)=\theta(x;1,1) θ ( x ) = θ ( x ; 1 , 1 ) [37 Theorems 1 and 2, p. 398] give, for q = 1 , 4 , 6 q=1,4,6 q = 1 , 4 , 6 ( a , q ) = 1 (a,q)=1 ( a , q ) = 1
max 1 ≤ t ≤ x ∣ θ ( t ; q , a ) − t φ ( q ) ∣ ≤ { 2.072 x , 1 ≤ x ≤ 10 10 , ε q x / φ ( q ) , x ≥ 10 10 , \max_{1\le t\le x}\left|\theta(t;q,a)-\frac{t}{\varphi(q)}\right|
\le
\begin{cases}
2.072\sqrt{x}, & 1\le x\le10^{10},\\
\varepsilon_qx/\varphi(q), & x\ge10^{10},
\end{cases} 1 ≤ t ≤ x max θ ( t ; q , a ) − φ ( q ) t ≤ { 2.072 x , ε q x / φ ( q ) , 1 ≤ x ≤ 1 0 10 , x ≥ 1 0 10 , where ε 1 = 0.000213 \varepsilon_1=0.000213 ε 1 = 0.000213 ε 4 = ε 6 = 0.004560 \varepsilon_4=\varepsilon_6=0.004560 ε 4 = ε 6 = 0.004560 x = u x=u x = u 10 10 10^{10} 1 0 10
Since 4.144 4 / 3 < 24 / 5 < 5 4.144\sqrt{4/3}<24/5<5 4.144 4/3 < 24/5 < 5 q = 4 , 6 q=4,6 q = 4 , 6 θ ( u ; q , a ) − θ ( ℓ ; q , a ) \theta(u;q,a)-\theta(\ell;q,a) θ ( u ; q , a ) − θ ( ℓ ; q , a )
{ n / 6 − 1 / 2 − 5 n , u ≤ 10 10 , ( 1 / 6 − 0.006080 ) n − 1 / 2 , u ≥ 10 10 . \begin{cases}
n/6-1/2-5\sqrt{n}, & u\le10^{10},\\
(1/6-0.006080)n-1/2, & u\ge10^{10}.
\end{cases} { n /6 − 1/2 − 5 n , ( 1/6 − 0.006080 ) n − 1/2 , u ≤ 1 0 10 , u ≥ 1 0 10 . Both are positive for n ≥ 1000 n\ge1000 n ≥ 1000 1000 1000 1000 37 / 6 37/6 37/6 1000 < 32 \sqrt{1000}<32 1000 < 32
For q = 1 q=1 q = 1 n ≥ 16384 = 2 14 n\ge16384=2^{14} n ≥ 16384 = 2 14
θ ( u ) − θ ( ℓ ) n > 1 3 − 1 16384 − 3 80 . \frac{\theta(u)-\theta(\ell)}{n}>\frac{1}{3}-\frac{1}{16384}-\frac{3}{80}. n θ ( u ) − θ ( ℓ ) > 3 1 − 16384 1 − 80 3 . Indeed, in the lower range the error is less than 24 / ( 5 n ) ≤ 3 / 80 24/(5\sqrt{n}) \le3/80 24/ ( 5 n ) ≤ 3/80 0.000568 < 3 / 80 0.000568 < 3/80 0.000568 < 3/80 log n > 9 \log n > 9 log n > 9 log ( 4 / 3 ) < 3 / 10 \log(4/3) < 3/10 log ( 4/3 ) < 3/10 log n / log u > 30 / 31 \log n/\log u > 30/31 log n / log u > 30/31
π ( I n ) log n n ≥ θ ( u ) − θ ( ℓ ) n log n log u > 30 31 ( 1 3 − 1 16384 − 3 80 ) = 72689 253952 > 2 7 . \pi(I_n)\frac{\log n}{n} \ge\frac{\theta(u)-\theta(\ell)}{n}\frac{\log n}{\log u} > \frac{30}{31}\left(\frac{1}{3}-\frac{1}{16384}-\frac{3}{80}\right)=\frac{72689}{253952}>\frac{2}{7}. π ( I n ) n log n ≥ n θ ( u ) − θ ( ℓ ) log u log n > 31 30 ( 3 1 − 16384 1 − 80 3 ) = 253952 72689 > 7 2 . For the finite range we use the prime sets in Table 3 . Each row has the following properties: all listed primes belong to I n I_n I n ( p − 1 ) / 2 (p-1)/2 ( p − 1 ) /2 33 ≤ n ≤ 17325 33 \le n \le17325 33 ≤ n ≤ 17325
Table 3. Prime sets with gcd { ( p − 1 ) / 2 } = 1 \gcd\{(p-1)/2\}=1 g cd{( p − 1 ) /2 } = 1
Excluding smaller blocks
Suppose a permutation group preserves blocks of size m m m d d d d > m d>m d > m m ∣ d m \mid d m ∣ d
By Seki’s theorem the group G n = Gal ( Q n / Q ) G_n=\operatorname{Gal}(\mathbb{Q}_n/\mathbb{Q}) G n = Gal ( Q n / Q ) n ≥ 33 n \ge33 n ≥ 33 2 ≤ m ≤ n / 3 2 \le m \le n/3 2 ≤ m ≤ n /3 m ∣ n m \mid n m ∣ n p ∈ I n p \in I_n p ∈ I n d = n − ( p − 1 ) / 2 > n / 3 ≥ m d=n-(p-1)/2>n/3\ge m d = n − ( p − 1 ) /2 > n /3 ≥ m
p ≡ 1 ( m o d 2 m ) ( p ∈ I n ) . (49) p \equiv1 \pmod{2m}\qquad(p\in I_n). \tag*{(49)} p ≡ 1 ( mod 2 m ) ( p ∈ I n ) . (49) For 33 ≤ n < 16384 33 \le n < 16384 33 ≤ n < 16384 Table 3 .
Now let n ≥ 16384 n \ge16384 n ≥ 16384 Lemma 5.3 excludes m = 2 , 3 m=2,3 m = 2 , 3 m ≥ 4 m \ge4 m ≥ 4 φ ( 2 m ) ≥ 4 \varphi(2m) \ge4 φ ( 2 m ) ≥ 4 y = ( n − 3 ) / 3 y=(n-3)/3 y = ( n − 3 ) /3 M = y / ( 2 n 3 / 5 ) M=y/(2n^{3/5}) M = y / ( 2 n 3/5 ) m ≤ M m \le M m ≤ M [31 Theorem 2, (1.10)] gives
π ( I n ) < 2 y φ ( 2 m ) log ( y / ( 2 m ) ) ≤ 5 y 6 log n < 5 n 18 log n < 2 n 7 log n , \pi(I_n)<\frac{2y}{\varphi(2m)\log(y/(2m))}\le\frac{5y}{6\log n}<\frac{5n}{18\log n}<\frac{2n}{7\log n}, π ( I n ) < φ ( 2 m ) log ( y / ( 2 m )) 2 y ≤ 6 log n 5 y < 18 log n 5 n < 7 log n 2 n , contrary to (48) . Here y / ( 2 m ) ≥ n 3 / 5 > 1 y/(2m)\ge n^{3/5}>1 y / ( 2 m ) ≥ n 3/5 > 1 m > M m>M m > M (49) contains at most y / ( 2 m ) + 1 < n 3 / 5 + 1 y/(2m)+1<n^{3/5}+1 y / ( 2 m ) + 1 < n 3/5 + 1 I n I_n I n n ≥ 16384 n\ge16384 n ≥ 16384
( n − 2 / 5 + n − 1 ) log n < 2 7 . \left(n^{-2/5}+n^{-1}\right)\log n<\frac{2}{7}. ( n − 2/5 + n − 1 ) log n < 7 2 . since the left side decreases on this range, and at the left endpoint it is less than 10 ( 1 / 40 + 1 / 16384 ) = 2053 / 8192 < 2 / 7 10(1/40 + 1/16384) = 2053/8192 < 2/7 10 ( 1/40 + 1/16384 ) = 2053/8192 < 2/7 log 16384 < 10 \log16384 < 10 log 16384 < 10 16384 2 / 5 > 40 16384^{2/5} > 40 1638 4 2/5 > 40 (48) . The only proper divisor of n n n n / 3 n/3 n /3 n / 2 n/2 n /2
Excluding two blocks by their traces
Suppose now that n ≥ 33 n \ge33 n ≥ 33 n / 2 n/2 n /2 A , B A, B A , B
A + B = − 1 , T = A B ∈ Z , ∣ T ∣ < 4 n 2 . A+B=-1,\qquad T=AB\in\mathbb{Z},\qquad|T|<4n^2. A + B = − 1 , T = A B ∈ Z , ∣ T ∣ < 4 n 2 . The integrality follows because T T T (44) .
Let L L L n + 1 < p ≤ 2 n n+1<p\le2n n + 1 < p ≤ 2 n p \mathfrak{p} p L L L p p p R R R d d d p \mathfrak{p} p d > 1 d>1 d > 1 R R R d = 1 d=1 d = 1 R R R R R R
An arithmetic Frobenius lift thus permutes the unit roots in each block. If a block has h h h S S S p \mathfrak{p} p S p = S S^p=S S p = S (46) gives S p = 4 h − S S^p=4h-S S p = 4 h − S S = 2 h S=2h S = 2 h n / 2 n/2 n /2 n / 2 − d n/2-d n /2 − d A , B A,B A , B n n n n − 2 d n-2d n − 2 d T ∈ Z T\in\mathbb{Z} T ∈ Z p ∩ Z = p Z \mathfrak{p}\cap\mathbb{Z}=p\mathbb{Z} p ∩ Z = p Z
T = n ( n − 2 d ) = n ( p − 1 − n ) ≡ − n ( n + 1 ) ( m o d p ) . T=n(n-2d)=n(p-1-n)\equiv-n(n+1)\pmod{p}. T = n ( n − 2 d ) = n ( p − 1 − n ) ≡ − n ( n + 1 ) ( mod p ) . For n ≥ 24 n\ge24 n ≥ 24 [33 Theorem, p. 180] give distinct primes
n + 1 < p 1 < p 2 < p 3 < ( 6 / 5 ) 3 ( n + 1 ) < 2 n . n+1<p_1<p_2<p_3<(6/5)^3(n+1)<2n. n + 1 < p 1 < p 2 < p 3 < ( 6/5 ) 3 ( n + 1 ) < 2 n . Consequently
∏ n + 1 < p ≤ 2 n p > ( n + 1 ) 3 > 5 n 2 + n . \prod_{n+1<p\le2n}p>(n+1)^3>5n^2+n. n + 1 < p ≤ 2 n ∏ p > ( n + 1 ) 3 > 5 n 2 + n . This product divides the integer T + n ( n + 1 ) T+n(n+1) T + n ( n + 1 ) 5 n 2 + n 5n^2+n 5 n 2 + n T = − n ( n + 1 ) T=-n(n+1) T = − n ( n + 1 ) A , B A,B A , B n , − n − 1 n,-n-1 n , − n − 1 Z 2 + Z − n ( n + 1 ) Z^2+Z-n(n+1) Z 2 + Z − n ( n + 1 ) G n G_n G n n ≥ 33 n\ge33 n ≥ 33
The symmetric group in every degree
For every n ≥ 33 n\ge33 n ≥ 33 Table 3 and Lemma 5.3 supply a prime p ∈ I n p\in I_n p ∈ I n p ≡ 2 n + 1 ( m o d 4 ) p\equiv2n+1\pmod{4} p ≡ 2 n + 1 ( mod 4 ) d = ( 2 n + 1 − p ) / 2 d=(2n+1-p)/2 d = ( 2 n + 1 − p ) /2 2 ≤ d < n / 2 2\le d<n/2 2 ≤ d < n /2 Lemma 3.2 yields A n ⊆ G n A_n\subseteq G_n A n ⊆ G n G n = S n G_n=S_n G n = S n
For 3 ≤ n ≤ 32 3\le n\le32 3 ≤ n ≤ 32 Table 4 gives two squarefree reductions of Q n Q_n Q n p p p ( 1 , n − 1 ) (1,n-1) ( 1 , n − 1 ) λ q \lambda_q λ q q q q [30 Theorem 8.23] therefore supplies an ( n − 1 ) (n-1) ( n − 1 ) ( n − 1 ) (n-1) ( n − 1 ) S n S_n S n
Table 4. Squarefree factorizations of Q n Q_n Q n p p p ( 1 , n − 1 ) (1,n-1) ( 1 , n − 1 ) λ q \lambda_q λ q
For a squarefree polynomial f ∈ F p [ x ] f\in\mathbb{F}_p[x] f ∈ F p [ x ] x p j − x x^{p^j}-x x p j − x j j j
An explicit bound over a number field
We claim that for every n ≥ 2 n \ge2 n ≥ 2 p > n p > n p > n P n P_n P n n ≥ 33 n \ge33 n ≥ 33 n + 1 < p < 2 n n+1 < p < 2n n + 1 < p < 2 n p ≡ 2 n + 1 ( m o d 4 ) p \equiv2n+1 \pmod{4} p ≡ 2 n + 1 ( mod 4 ) 7 ≤ n ≤ 32 7 \le n \le32 7 ≤ n ≤ 32
Table 5.
At n = 5 n = 5 n = 5 p = 7 p = 7 p = 7
Table 6.
In each row p > n p > n p > n v p ( Disc ( P n ) ) = 1 v_p(\operatorname{Disc}(P_n)) = 1 v p ( Disc ( P n )) = 1 p p p
For n ≥ max { 2 , R F } n \ge\max\{2, R_F\} n ≥ max { 2 , R F } p > n p > n p > n F F F Lemma 3.10 (1) gives Gal F ( P n ) = S n \operatorname{Gal}_F(P_n) = \mathfrak{S}_n Gal F ( P n ) = S n
Gal F ( P n ) = S n ( n ≥ R F ) . (50) \operatorname{Gal}_F(P_n) = \mathfrak{S}_n \qquad(n \ge R_F). \tag*{(50)} Gal F ( P n ) = S n ( n ≥ R F ) . (50) This completes the proof of Theorem E.
Arithmetic families
We begin with a family of rational functions whose coefficients are eventually constant. Their sections are quotients of trinomials, and their Galois groups can be determined by the classical inertia and transposition argument; compare [42 Section 4.4, Remark 2] . The following consequence of Minkowski’s bound will control ramification at 2.
Lemma 6.1. A number field unramified at every odd prime and tamely ramified at 2 is Q \mathbb{Q} Q
Proof. Suppose the field has degree d ≥ 2 d \ge2 d ≥ 2 D D D r 2 r_2 r 2 ∣ D ∣ ≤ 2 d − 1 |D| \le2^{d-1} ∣ D ∣ ≤ 2 d − 1 [30 Theorem 4.3] gives
∣ D ∣ ≥ ( π / 4 ) 2 r 2 ( d d / d ! ) 2 ≥ ( π / 4 ) d ( d d / d ! ) 2 ≥ π d / 4 > 2 d − 1 . |D| \ge(\pi/4)^{2r_2}(d^d/d!)^2 \ge(\pi/4)^d(d^d/d!)^2 \ge\pi^d/4 > 2^{d-1}. ∣ D ∣ ≥ ( π /4 ) 2 r 2 ( d d / d ! ) 2 ≥ ( π /4 ) d ( d d / d ! ) 2 ≥ π d /4 > 2 d − 1 . The inequality d d / d ! ≥ 2 d − 1 d^d/d! \ge2^{d-1} d d / d ! ≥ 2 d − 1 ( 1 + 1 / d ) d ≥ 2 (1+1/d)^d \ge2 ( 1 + 1/ d ) d ≥ 2 d = 2 d=2 d = 2
For the family below, parity detects the reducible sections. In the remaining degrees, the preceding lemma allows us to recover the whole group from inertia at odd primes.
Proposition 6.2. Let k = 2 a k=2^a k = 2 a a a a h k = ( 1 + x k ) / ( 1 − x ) h_k=(1+x^k)/(1-x) h k = ( 1 + x k ) / ( 1 − x ) n ≥ k n \ge k n ≥ k
Gal ( ( h k ) n / Q ) = S n if n is even , ( h k ) n ( − 1 ) = 0 if n is odd . \operatorname{Gal}((h_k)_n/\mathbb{Q})=\mathfrak{S}_n \quad\text{if } n \text{ is even}, \qquad(h_k)_n(-1)=0 \quad\text{if } n \text{ is odd}. Gal (( h k ) n / Q ) = S n if n is even , ( h k ) n ( − 1 ) = 0 if n is odd . Consequently ( S ( h k ) , A ( h k ) , O ( h k ) ) = ( 1 / 2 , 0 , 1 / 2 ) (S(h_k),A(h_k),O(h_k))=(1/2,0,1/2) ( S ( h k ) , A ( h k ) , O ( h k )) = ( 1/2 , 0 , 1/2 )
Proof. Put N = n + 1 N=n+1 N = n + 1 m = N − k m=N-k m = N − k
x n ( h k ) n ( 1 / x ) = Q ( x ) : = x N + x m − 2 x − 1 . (51) x^n(h_k)_n(1/x)=Q(x):=\frac{x^N+x^m-2}{x-1}. \tag*{(51)} x n ( h k ) n ( 1/ x ) = Q ( x ) := x − 1 x N + x m − 2 . (51) If n n n N , m N,m N , m Q ( − 1 ) = 0 Q(-1)=0 Q ( − 1 ) = 0 n n n N , m N,m N , m gcd ( N , m ) = 1 \gcd(N,m)=1 g cd( N , m ) = 1
The polynomial R = x N + x m − 2 R=x^N+x^m-2 R = x N + x m − 2 x N = x m = 1 x^N=x^m=1 x N = x m = 1 x = 1 x=1 x = 1 R ′ ( 1 ) = N + m > 0 R'(1)=N+m>0 R ′ ( 1 ) = N + m > 0 Q Q Q Q ( 0 ) = 2 Q(0)=2 Q ( 0 ) = 2 Q Q Q
Fix an odd prime p p p α ∈ F p \alpha\in\mathbb{F}_p α ∈ F p R R R α ≠ 0 \alpha\ne0 α = 0
α N + α m = 2 , N α N + m α m = 0. \alpha^N+\alpha^m=2,\qquad N\alpha^N+m\alpha^m=0. α N + α m = 2 , N α N + m α m = 0. No such root exists if p ∣ N m ( N − m ) p\mid Nm(N-m) p ∣ N m ( N − m )
α N = − 2 m / ( N − m ) , α m = 2 N / ( N − m ) . \alpha^N=-2m/(N-m),\qquad\alpha^m=2N/(N-m). α N = − 2 m / ( N − m ) , α m = 2 N / ( N − m ) . Coprimality of N , m N,m N , m α 2 R ′ ′ ( α ) = − 2 N m ≠ 0 \alpha^2R''(\alpha)=-2Nm\ne0 α 2 R ′′ ( α ) = − 2 N m = 0 x − 1 x-1 x − 1 Q Q Q
At 2,
Q ( x ) ≡ x m ( x + 1 ) k − 1 ( m o d 2 ) . Q(x)\equiv x^m(x+1)^{k-1}\pmod{2}. Q ( x ) ≡ x m ( x + 1 ) k − 1 ( mod 2 ) . Hensel factorization gives Q = A B Q=AB Q = A B Z 2 [ x ] \mathbb{Z}_2[x] Z 2 [ x ] A , B A,B A , B m , k − 1 m,k-1 m , k − 1 x m , ( x + 1 ) k − 1 x^m,(x+1)^{k-1} x m , ( x + 1 ) k − 1 Q ( 0 ) = 2 Q(0)=2 Q ( 0 ) = 2 B ( 0 ) B(0) B ( 0 ) A A A k = 2 k=2 k = 2 B B B k ≥ 4 k\ge4 k ≥ 4 v 2 ( Q ( 1 ) ) = v 2 ( 2 N − k ) = 1 v_2(Q(1))=v_2(2N-k)=1 v 2 ( Q ( 1 )) = v 2 ( 2 N − k ) = 1 A ( 1 ) A(1) A ( 1 ) B ( x + 1 ) B(x+1) B ( x + 1 ) [12 Theorem 2.1] . Hence the splitting field L L L Q Q Q
Let H H H Gal ( L / Q ) \operatorname{Gal}(L/\mathbb{Q}) Gal ( L / Q ) Lemma 6.1 makes it Q \mathbb{Q} Q S N − 1 \mathfrak{S}_{N-1} S N − 1
The case k = 2 k=2 k = 2 (5) , also shows that the coefficient tail does not determine the frequencies.
Corollary 6.3. Neither the frequency triple nor the zero–one property is invariant under changes to finitely many coefficients.
Proof. The series 2 / ( 1 − x ) 2/(1-x) 2/ ( 1 − x ) ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) 2 / ( 1 − x ) − h 2 = 1 + x 2/(1-x)-h_2=1+x 2/ ( 1 − x ) − h 2 = 1 + x
Remark 6.4. Nicholas Katz suggested considering the more general family
h N , k ( x ) = 1 + N x k 1 − x , N ∈ Z ≥ 1 , k ∈ Z ≥ 2 . h_{N,k}(x)=\frac{1+Nx^k}{1-x}, \qquad N\in\mathbb{Z}_{\geq1}, \qquad k\in\mathbb{Z}_{\geq2}. h N , k ( x ) = 1 − x 1 + N x k , N ∈ Z ≥ 1 , k ∈ Z ≥ 2 . For n ≥ k n\geq k n ≥ k
x n ( h N , k ) n ( 1 / x ) = x n + 1 + N x n + 1 − k − ( N + 1 ) x − 1 . x^n(h_{N,k})_n(1/x)=\frac{x^{n+1}+Nx^{n+1-k}-(N+1)}{x-1}. x n ( h N , k ) n ( 1/ x ) = x − 1 x n + 1 + N x n + 1 − k − ( N + 1 ) . If d = gcd ( n + 1 , k ) d=\gcd(n+1,k) d = g cd( n + 1 , k ) ( h N , k ) n (h_{N,k})_n ( h N , k ) n ( x d − 1 ) / ( x − 1 ) (x^d-1)/(x-1) ( x d − 1 ) / ( x − 1 ) ζ \zeta ζ ζ n + 1 = ζ n + 1 − k = 1 \zeta^{n+1}=\zeta^{n+1-k}=1 ζ n + 1 = ζ n + 1 − k = 1 ( n + 1 + N ( n + 1 − k ) ) ζ − 1 ≠ 0 (n+1+N(n+1-k))\zeta^{-1}\ne0 ( n + 1 + N ( n + 1 − k )) ζ − 1 = 0 k = 2 a k=2^a k = 2 a a ≥ 1 a\geq1 a ≥ 1 k k k x + 1 x+1 x + 1 k k k
We leave as a question here whether
( S ( h N , k ) , A ( h N , k ) , O ( h N , k ) ) = ( 1 / 2 , 0 , 1 / 2 ) ( N ≥ 1 , k = 2 a , a ≥ 1 ) . (S(h_{N,k}),A(h_{N,k}),O(h_{N,k}))=(1/2,0,1/2) \qquad(N\geq1,\ k=2^a,\ a\geq1). ( S ( h N , k ) , A ( h N , k ) , O ( h N , k )) = ( 1/2 , 0 , 1/2 ) ( N ≥ 1 , k = 2 a , a ≥ 1 ) . The stronger assertion that every even section of degree at least k k k N N N
( h 11 , 4 ) 4 ( x ) = 1 + x + x 2 + x 3 + 12 x 4 = ( 1 + 3 x + 4 x 2 ) ( 1 − 2 x + 3 x 2 ) . (h_{11,4})_4(x)=1+x+x^2+x^3+12x^4=(1+3x+4x^2)(1-2x+3x^2). ( h 11 , 4 ) 4 ( x ) = 1 + x + x 2 + x 3 + 12 x 4 = ( 1 + 3 x + 4 x 2 ) ( 1 − 2 x + 3 x 2 ) . This finite exception does not decide the frequency question.
Further exact rational families
For every fixed even k ≥ 2 k\geq2 k ≥ 2 u k = ( 2 x k − 1 ) / ( 1 − x ) u_k=(2x^k-1)/(1-x) u k = ( 2 x k − 1 ) / ( 1 − x )
( S ( u k ) , A ( u k ) , O ( u k ) ) = ( φ ( k ) / k , 0 , 1 − φ ( k ) / k ) . (52) (S(u_k),A(u_k),O(u_k))=(\varphi(k)/k,0,1-\varphi(k)/k). \tag*{(52)} ( S ( u k ) , A ( u k ) , O ( u k )) = ( φ ( k ) / k , 0 , 1 − φ ( k ) / k ) . (52) Its coefficients are − 1 -1 − 1 k k k N = n + 1 > k N=n+1>k N = n + 1 > k R ( x ) = x N − 2 x k + 1 = ( x − 1 ) ( u k ) n ( x ) R(x)=x^N-2x^k+1=(x-1)(u_k)_n(x) R ( x ) = x N − 2 x k + 1 = ( x − 1 ) ( u k ) n ( x ) d = gcd ( N , k ) > 1 d=\gcd(N,k)>1 d = g cd( N , k ) > 1 ( x d − 1 ) / ( x − 1 ) (x^d-1)/(x-1) ( x d − 1 ) / ( x − 1 ) gcd ( N , k ) = 1 \gcd(N,k)=1 g cd( N , k ) = 1 [39 ] makes the quotient by x − 1 x-1 x − 1 ( N , k ) = ( 7 , 2 ) (N,k)=(7,2) ( N , k ) = ( 7 , 2 ) ( 7 , 5 ) (7,5) ( 7 , 5 ) [19 p. 5] . We may therefore assume N > 7 N>7 N > 7 k k k N N N N k ( N − k ) Nk(N-k) N k ( N − k ) R R R R ′ ′ R'' R ′′ p ∤ N k ( N − k ) p\nmid Nk(N-k) p ∤ N k ( N − k ) α ∈ F ‾ p \alpha\in\overline{\mathbb{F}}_p α ∈ F p
α k = N 2 ( N − k ) , α N = k N − k , R ′ ′ ( α ) = 2 k ( N − k ) α k − 2 ≠ 0. \alpha^k=\frac{N}{2(N-k)},\qquad\alpha^N=\frac{k}{N-k},\qquad R''(\alpha)=2k(N-k)\alpha^{k-2}\ne0. α k = 2 ( N − k ) N , α N = N − k k , R ′′ ( α ) = 2 k ( N − k ) α k − 2 = 0. Since gcd ( N , k ) = 1 \gcd(N,k)=1 g cd( N , k ) = 1 α \alpha α Q \mathbb{Q} Q [30 Theorem 4.9] . Transitivity gives S ~ n \widetilde{S}_n S n gcd ( n + 1 , k ) = 1 \gcd(n+1,k)=1 g cd( n + 1 , k ) = 1 (52) .
For the positive family h k = ( 1 + x k ) / ( 1 − x ) h_k=(1+x^k)/(1-x) h k = ( 1 + x k ) / ( 1 − x ) [20 Theorem 1.1] , in its ∣ a b ∣ = 2 |ab|=2 ∣ ab ∣ = 2 k ≥ 1 k\geq1 k ≥ 1
( S ( h k ) , A ( h k ) , O ( h k ) ) = ( φ ( k ) / k , 0 , 1 − φ ( k ) / k ) . (53) (S(h_k),A(h_k),O(h_k))=(\varphi(k)/k,0,1-\varphi(k)/k). \tag*{(53)} ( S ( h k ) , A ( h k ) , O ( h k )) = ( φ ( k ) / k , 0 , 1 − φ ( k ) / k ) . (53) Indeed, for n ≥ k n\geq k n ≥ k N = n + 1 N=n+1 N = n + 1 (51) applies. When gcd ( N , k ) = 1 \gcd(N,k)=1 g cd( N , k ) = 1 x N + x N − k − 2 x^N+x^{N-k}-2 x N + x N − k − 2 1 1 1 S ~ N − 1 \widetilde{S}_{N-1} S N − 1 N > 8 N>8 N > 8 k k k Proposition 6.2 gives an independent proof for powers of two, including every degree n ≥ k n\geq k n ≥ k
Remark 6.6. Katz also pointed out the distinction between powers of two and other even exponents. For N = 1 N=1 N = 1 (53) gives, for every even k k k
S ( h k ) = φ ( k ) k = 1 2 ∏ p ∣ k p odd prime ( 1 − 1 p ) . S(h_k)=\frac{\varphi(k)}{k}=\frac{1}{2}\prod_{\substack{p\mid k\\p\ \text{odd prime}}}\left(1-\frac{1}{p}\right). S ( h k ) = k φ ( k ) = 2 1 p ∣ k p odd prime ∏ ( 1 − p 1 ) . This equals 1 / 2 1/2 1/2 k k k k k k gcd ( n + 1 , k ) > 1 \gcd(n+1,k)>1 g cd( n + 1 , k ) > 1
The ratios φ ( k ) / k \varphi(k)/k φ ( k ) / k [ 0 , 1 ] [0,1] [ 0 , 1 ] [16 Introduction] . Indeed, products of 1 − 1 / p 1-1/p 1 − 1/ p 1 / p 1/p 1/ p ( 0 , 1 ) (0,1) ( 0 , 1 ) (53) gives a dense set of triples on the edge ( t , 0 , 1 − t ) (t,0,1-t) ( t , 0 , 1 − t ) O ( h k ) ∈ { 0 , 1 } O(h_k)\in\{0,1\} O ( h k ) ∈ { 0 , 1 } k = 1 k=1 k = 1
For an integer r ≥ 0 r\geq0 r ≥ 0 f [ r ] = ∑ j ≥ 0 a j + r x j f^{[r]}=\sum_{j\geq0}a_{j+r}x^j f [ r ] = ∑ j ≥ 0 a j + r x j
h k [ r ] = { h k − r , r < k , 2 / ( 1 − x ) , r ≥ k . h_k^{[r]}=
\begin{cases}
h_{k-r}, & r<k,\\
2/(1-x), & r\geq k.
\end{cases} h k [ r ] = { h k − r , 2/ ( 1 − x ) , r < k , r ≥ k . Consequently, deleting a finite prefix need not preserve the frequency triple.
A rational family with other frequency one
A different mechanism occurs for coefficients with a geometric progression on each parity class. Odd sections factor, while even sections have a reciprocal symmetry that preserves pairs of roots.
Proposition 6.8. For a , b , c ∈ Q × a,b,c\in\mathbb{Q}^{\times} a , b , c ∈ Q ×
f ( x ) = a + b x 1 − c x 2 ⟹ ( S ( f ) , A ( f ) , O ( f ) ) = ( 0 , 0 , 1 ) . f(x)=\frac{a+bx}{1-cx^2}\Longrightarrow(S(f),A(f),O(f))=(0,0,1). f ( x ) = 1 − c x 2 a + b x ⟹ ( S ( f ) , A ( f ) , O ( f )) = ( 0 , 0 , 1 ) . Proof. Odd sections factor as ( a + b x ) ∑ j = 0 m ( c x 2 ) j (a+bx)\sum_{j=0}^{m}(cx^2)^j ( a + b x ) ∑ j = 0 m ( c x 2 ) j c m x 2 m f 2 m ( 1 / ( c x ) ) = f 2 m ( x ) c^m x^{2m}f_{2m}(1/(cx))=f_{2m}(x) c m x 2 m f 2 m ( 1/ ( c x )) = f 2 m ( x ) α ↦ 1 / ( c α ) \alpha\mapsto1/(c\alpha) α ↦ 1/ ( c α ) S 2 m \mathfrak{S}_{2m} S 2 m S ~ 2 m \widetilde{S}_{2m} S 2 m
This includes every nonzero two-periodic rational coefficient sequence. For period d ≥ 3 d\geq3 d ≥ 3 f = P ( x ) / ( 1 − x d ) f=P(x)/(1-x^d) f = P ( x ) / ( 1 − x d ) deg P = d − 1 \deg P=d-1 deg P = d − 1 d − 1 d-1 d − 1 d d d P ( x ) ∑ j = 0 m x d j P(x)\sum_{j=0}^{m}x^{dj} P ( x ) ∑ j = 0 m x d j 1 / d 1/d 1/ d
Exponential and logarithm
Schur’s theorem gives
G n ( e x ) = { A n , 4 ∣ n , S n , 4 ∤ n , ( S ( e x ) , A ( e x ) , O ( e x ) ) = ( 3 / 4 , 1 / 4 , 0 ) . G_n(e^x)=
\begin{cases}
\mathcal{A}_n, & 4\mid n,\\
\mathcal{S}_n, & 4\nmid n,
\end{cases}
\qquad
(S(e^x),A(e^x),O(e^x))=(3/4,1/4,0). G n ( e x ) = { A n , S n , 4 ∣ n , 4 ∤ n , ( S ( e x ) , A ( e x ) , O ( e x )) = ( 3/4 , 1/4 , 0 ) . See [40 , 11 ] and [36 Theorem 1.1] . With e n ( x ) = ∑ j = 0 n x j / j ! e_n(x)=\sum_{j=0}^{n}x^j/j! e n ( x ) = ∑ j = 0 n x j / j !
Disc ( n ! e n ) = ( − 1 ) n ( n − 1 ) / 2 ( n ! ) n , Disc ( e n ) = ( − 1 ) n ( n − 1 ) / 2 ( n ! ) 2 − n . \operatorname{Disc}(n!e_n)=(-1)^{n(n-1)/2}(n!)^n,\qquad
\operatorname{Disc}(e_n)=(-1)^{n(n-1)/2}(n!)^{2-n}. Disc ( n ! e n ) = ( − 1 ) n ( n − 1 ) /2 ( n ! ) n , Disc ( e n ) = ( − 1 ) n ( n − 1 ) /2 ( n ! ) 2 − n . The separate frequencies can change after extending the ground field. For every fixed number field F F F
( S F ( e x ) , A F ( e x ) , O F ( e x ) ) = { ( 1 / 2 , 1 / 2 , 0 ) , i ∈ F , ( 3 / 4 , 1 / 4 , 0 ) , i ∉ F . (54) (S_F(e^x),A_F(e^x),O_F(e^x))=
\begin{cases}
(1/2,1/2,0), & i\in F,\\
(3/4,1/4,0), & i\notin F.
\end{cases} \tag*{(54)} ( S F ( e x ) , A F ( e x ) , O F ( e x )) = { ( 1/2 , 1/2 , 0 ) , ( 3/4 , 1/4 , 0 ) , i ∈ F , i ∈ / F . (54) Indeed, Proposition 3.9 gives alternating containment in all large degrees. For even n n n [ ( − 1 ) n / 2 ] [(-1)^{n/2}] [( − 1 ) n /2 ] n n n n / 2 < p < n n/2<p<n n /2 < p < n v p ( n ! ) = 1 v_p(n!)=1 v p ( n !) = 1 n n n F F F F F F (54) and illustrates why the invariant other frequency does not force the separate frequencies to be invariant.
For every fixed integer a > 0 a>0 a > 0 [47 Theorem 1.1] proves the density-one result
E a ( x ) = ∑ j ≥ 0 x j ( a + j ) ! , ( S ( E a ) , A ( E a ) , O ( E a ) ) = ( 1 , 0 , 0 ) . E_a(x)=\sum_{j\geq0}\frac{x^j}{(a+j)!},\qquad
(S(E_a),A(E_a),O(E_a))=(1,0,0). E a ( x ) = j ≥ 0 ∑ ( a + j )! x j , ( S ( E a ) , A ( E a ) , O ( E a )) = ( 1 , 0 , 0 ) . For L ( x ) = 1 − log ( 1 − x ) L(x)=1-\log(1-x) L ( x ) = 1 − log ( 1 − x ) [43 ] ; see also [13 Section 1] . Hence O ( L ) = 0 O(L)=0 O ( L ) = 0 S n \mathcal{S}_n S n n ≡ 0 , 2 , 3 ( m o d 4 ) n\equiv0,2,3\pmod4 n ≡ 0 , 2 , 3 ( mod 4 ) [13 Theorem 1] , so
lim inf N → ∞ s L ( N ) ≥ 3 / 4 , lim sup N → ∞ a L ( N ) ≤ 1 / 4. \liminf_{N\to\infty}s_L(N)\geq3/4,\qquad
\limsup_{N\to\infty}a_L(N)\leq1/4. N → ∞ lim inf s L ( N ) ≥ 3/4 , N → ∞ lim sup a L ( N ) ≤ 1/4. Convergence of the first two frequencies is equivalent to the existence of a square-discriminant density. Cullinan and Gajek-Leonard also prove symmetry in degree m q mq m q m m m q q q [13 Theorem 3] . These families do not by themselves determine a density in the degree variable.
Factorial denominators and bounded multipliers
The next result combines Allen–Filaseta’s irreducibility theorems with explicit Newton polygons. It includes two Mittag–Leffler families and permits arbitrary bounded nonzero integer multipliers.
Proposition 6.11. Let B ≥ 1 B\geq1 B ≥ 1 ( b j ) (b_j) ( b j ) ∣ b 0 ∣ = 1 |b_0|=1 ∣ b 0 ∣ = 1 ∣ b j ∣ ≤ B |b_j|\leq B ∣ b j ∣ ≤ B F F F d F d_F d F B F = min { d F + 1 , 2 R F } B_F=\min\{d_F+1,2R_F\} B F = min { d F + 1 , 2 R F } m ≥ 1 m\geq1 m ≥ 1
N 1 = max { 50 , 4 m , 2 B , B F } . N_1=\max\{50,4m,2B,B_F\}. N 1 = max { 50 , 4 m , 2 B , B F } . The degree-n n n ∑ j ≥ 0 b j x j / ( m j ) ! \sum_{j\geq0}b_jx^j/(mj)! ∑ j ≥ 0 b j x j / ( mj )! A n \mathcal{A}_n A n F F F n ≥ N 1 n\geq N_1 n ≥ N 1 m ≥ 2 m\geq2 m ≥ 2
N 2 = ⌈ max { 179386 , 4 m + 1 , 2 B , 2 exp ( ( 2 m ) 1 / 3 ) , B F } ⌉ . N_2=\left\lceil\max\{179386,4m+1,2B,2\exp((2m)^{1/3}),B_F\}\right\rceil. N 2 = ⌈ max { 179386 , 4 m + 1 , 2 B , 2 exp (( 2 m ) 1/3 ) , B F } ⌉ . Write u ( r ) u_{(r)} u ( r ) u u u r r r
E m , B = { n ≥ 1 : ( m n + 1 ) ( 2 ) ≤ B or ( m n ( m n + 1 ) ) ( 6 ) ≤ B } . \mathcal{E}_{m,B}=\{n\geq1:(mn+1)_{(2)}\leq B\ \text{or}\ (mn(mn+1))_{(6)}\leq B\}. E m , B = { n ≥ 1 : ( mn + 1 ) ( 2 ) ≤ B or ( mn ( mn + 1 ) ) ( 6 ) ≤ B } . The degree-n n n ∑ j ≥ 0 b j x j / ( m j + 1 ) ! \sum_{j\geq0}b_jx^j/(mj+1)! ∑ j ≥ 0 b j x j / ( mj + 1 )! A n \mathcal{A}_n A n F F F n ≥ N 2 n\geq N_2 n ≥ N 2 n ∉ E m , B n\notin\mathcal{E}_{m,B} n ∈ / E m , B X ≥ 1 X\geq1 X ≥ 1 log r x = ( log x ) / ( log r ) \log_r x=(\log x)/(\log r) log r x = ( log x ) / ( log r )
# ( E m , B ∩ [ 1 , X ] ) ≤ B ( 1 + ⌊ log 2 ( m X + 1 ) ⌋ ) + 2 B ( 1 + ⌊ log 3 ( m X + 1 ) ⌋ ) . \#(\mathcal{E}_{m,B}\cap[1,X])\leq B(1+\lfloor\log_2(mX+1)\rfloor)+2B(1+\lfloor\log_3(mX+1)\rfloor). # ( E m , B ∩ [ 1 , X ]) ≤ B ( 1 + ⌊ log 2 ( m X + 1 )⌋) + 2 B ( 1 + ⌊ log 3 ( m X + 1 )⌋) . For m = 2 , 3 m = 2,3 m = 2 , 3 N 2 = max { 50 , 4 m + 1 , 2 B , B F } N_2 = \max\{50,4m+1,2B,B_F\} N 2 = max { 50 , 4 m + 1 , 2 B , B F } B = 1 B=1 B = 1 m m m n ≥ N 2 n \ge N_2 n ≥ N 2 O F = 0 O_F=0 O F = 0
Proof. Let P n P_n P n D = m n D=mn D = mn P n ( x m ) = ∑ i = 0 D a i x i / i ! P_n(x^m)=\sum_{i=0}^{D}a_i x^i/i! P n ( x m ) = ∑ i = 0 D a i x i / i ! P n ( x m ) = ∑ i = 0 D a i x i / ( i + 1 ) ! P_n(x^m)=\sum_{i=0}^{D}a_i x^i/(i+1)! P n ( x m ) = ∑ i = 0 D a i x i / ( i + 1 )! a m j = b j a_{mj}=b_j a mj = b j a i a_i a i [1 Theorems 1 and 2] . For the first family, D ≥ 50 D \ge50 D ≥ 50 ∣ b n ∣ ≤ B < D |b_n| \le B < D ∣ b n ∣ ≤ B < D n ∉ E m , B n \notin\mathcal{E}_{m,B} n ∈ / E m , B P n ( x m ) P_n(x^m) P n ( x m ) P n P_n P n
For n ≥ N 1 n \ge N_1 n ≥ N 1 n / 2 < p < 3 n / 5 < n − 2 n/2 < p < 3n/5 < n-2 n /2 < p < 3 n /5 < n − 2 n = 50 n=50 n = 50 p = 29 p=29 p = 29 p > m , B p>m,B p > m , B p 2 > m n p^2>mn p 2 > mn p > B p>B p > B b j b_j b j p p p − ⌊ m j / p ⌋ -\lfloor mj/p\rfloor − ⌊ mj / p ⌋ y = − m x / p y=-mx/p y = − m x / p j = 0 , p j=0,p j = 0 , p − m / p -m/p − m / p p p p
For the second family, Dusart’s explicit prime interval [15 Proposition 5.4] supplies, for every x ≥ 89693 x \ge89693 x ≥ 89693 x < p ≤ x ( 1 + 1 / log 3 x ) x<p\le x(1+1/\log^3 x) x < p ≤ x ( 1 + 1/ log 3 x ) x = n / 2 x=n/2 x = n /2 N 2 N_2 N 2
n 2 < p ≤ n 2 ( 1 + 1 2 m ) < m n 2 m − 1 < n − 2. \frac{n}{2}<p\le\frac{n}{2}\left(1+\frac{1}{2m}\right)<\frac{mn}{2m-1}<n-2. 2 n < p ≤ 2 n ( 1 + 2 m 1 ) < 2 m − 1 mn < n − 2. Also p > m , B p>m,B p > m , B p 2 > m n + 1 p^2>mn+1 p 2 > mn + 1 t ∈ { 1 , … , m − 1 } t\in\{1,\ldots,m-1\} t ∈ { 1 , … , m − 1 } t p ≡ 1 ( m o d m ) tp\equiv1\pmod m tp ≡ 1 ( mod m ) j 0 = ( t p − 1 ) / m j_0=(tp-1)/m j 0 = ( tp − 1 ) / m − ⌊ ( m j + 1 ) / p ⌋ -\lfloor(mj+1)/p\rfloor − ⌊( mj + 1 ) / p ⌋ y = − ( m x + 1 ) / p y=-(mx+1)/p y = − ( m x + 1 ) / p j ≡ j 0 ( m o d p ) j\equiv j_0\pmod p j ≡ j 0 ( mod p ) 0 ≤ j 0 < p 0\le j_0<p 0 ≤ j 0 < p 2 p > n 2p>n 2 p > n j 0 + p < ( 2 m − 1 ) p / m < n j_0+p<(2m-1)p/m<n j 0 + p < ( 2 m − 1 ) p / m < n j 0 , j 0 + p j_0,j_0+p j 0 , j 0 + p − m / p -m/p − m / p p p p m = 2 , 3 m=2,3 m = 2 , 3 n / 2 < p < 3 n / 5 ≤ m n / ( 2 m − 1 ) n/2<p<3n/5\le mn/(2m-1) n /2 < p < 3 n /5 ≤ mn / ( 2 m − 1 )
Lemma 3.7 now gives alternating containment over Q \mathbb{Q} Q n > d F n>d_F n > d F Proposition 3.9 gives the same conclusion over F F F n ≥ 2 R F n\ge2R_F n ≥ 2 R F p > n / 2 p>n/2 p > n /2 F F F p p p p p p p p p 2 p > n 2p>n 2 p > n Lemma 3.10 (2) then gives alternating containment over F F F B F B_F B F
For the exceptional count, the first condition has the form m n + 1 = δ 2 u mn+1=\delta2^u mn + 1 = δ 2 u 1 ≤ δ ≤ B 1\le\delta\le B 1 ≤ δ ≤ B m n , m n + 1 mn,mn+1 mn , mn + 1 δ 3 v \delta3^v δ 3 v 1 ≤ δ ≤ B 1\le\delta\le B 1 ≤ δ ≤ B m n = δ 3 v mn=\delta3^v mn = δ 3 v 3 v − 1 3^v-1 3 v − 1 ∣ b n ∣ = 1 |b_n|=1 ∣ b n ∣ = 1 D > 8 D>8 D > 8 [1 Theorem 2] leaves only D + 1 D+1 D + 1 m m m D + 1 > 1 D+1>1 D + 1 > 1 □ \square □
In particular,
E m , 1 ( x ) = ∑ j ≥ 0 x j ( m j ) ! , E m , 2 ( x ) = ∑ j ≥ 0 x j ( m j + 1 ) ! E_{m,1}(x)=\sum_{j\ge0}\frac{x^j}{(mj)!},\qquad E_{m,2}(x)=\sum_{j\ge0}\frac{x^j}{(mj+1)!} E m , 1 ( x ) = j ≥ 0 ∑ ( mj )! x j , E m , 2 ( x ) = j ≥ 0 ∑ ( mj + 1 )! x j have O F = 0 O_F=0 O F = 0 m ≥ 1 m\ge1 m ≥ 1 m ≥ 2 m\ge2 m ≥ 2 cos x = E 2 , 1 ( − x ) \cos\sqrt{x}=E_{2,1}(-x) cos x = E 2 , 1 ( − x ) sin x / x = E 2 , 2 ( − x ) \sin\sqrt{x}/\sqrt{x}=E_{2,2}(-x) sin x / x = E 2 , 2 ( − x ) x = 0 x=0 x = 0 m = 1 m=1 m = 1 E m , 2 E_{m,2} E m , 2
Reciprocal factorial powers
For a fixed integer k ≥ 1 k\ge1 k ≥ 1
F k ( x ) = ∑ j ≥ 0 x j ( j ! ) k = 0 F k − 1 ( 1 , … , 1 ; x ) . F_k(x)=\sum_{j\ge0}\frac{x^j}{(j!)^k}={}_0F_{k-1}(1,\ldots,1;x). F k ( x ) = j ≥ 0 ∑ ( j ! ) k x j = 0 F k − 1 ( 1 , … , 1 ; x ) . For n ≥ max { 50 , 2 k } n \ge\max\{50,2k\} n ≥ max { 50 , 2 k } Q \mathbb{Q} Q Q \mathbb{Q} Q n / 2 < p < 3 n / 5 < n − 2 n/2 < p < 3n/5 < n-2 n /2 < p < 3 n /5 < n − 2 p > k p > k p > k ( 0 , 0 ) (0,0) ( 0 , 0 ) ( p , − k ) (p,-k) ( p , − k ) p p p Lemma 3.7 proves the assertion. Over a number field F F F n ≥ max { 50 , 2 k , B F } n \ge\max\{50,2k,B_F\} n ≥ max { 50 , 2 k , B F } B F = min { [ F : Q ] + 1 , 2 R F } B_F=\min\{[F:\mathbb{Q}]+1,2R_F\} B F = min {[ F : Q ] + 1 , 2 R F } F F F Q \mathbb{Q} Q O F ( F k ) O_F(F_k) O F ( F k ) O F ( F k ) O_F(F_k) O F ( F k ) { 0 , 1 } \{0,1\} { 0 , 1 } F F F k = 2 k=2 k = 2 I 0 ( 2 x ) I_0(2\sqrt{x}) I 0 ( 2 x )
The same exact reduction applies to 1 + Li k ( x ) = 1 + ∑ j ≥ 1 x j / j k 1+\operatorname{Li}_k(x)=1+\sum_{j\ge1}x^j/j^k 1 + Li k ( x ) = 1 + ∑ j ≥ 1 x j / j k k ≥ 1 k\ge1 k ≥ 1 n / 2 < p < n − 2 n/2<p<n-2 n /2 < p < n − 2 p > k p>k p > k − k -k − k j = p j=p j = p ( 0 , 0 ) (0,0) ( 0 , 0 ) ( p , − k ) (p,-k) ( p , − k ) k = 1 k=1 k = 1
Frequencies and effective constructions
We first express the frequency problem through alternating containment and discriminant square classes. We then draw the consequences of simultaneous prescription and consider effective questions.
Two arithmetic means
Put ι n = C ( f n ) \iota_n=C(f_n) ι n = C ( f n ) n ≥ 8 n\ge8 n ≥ 8 ι n = 0 \iota_n=0 ι n = 0 n n n F F F
D n , F = 1 { Disc ( f n ) ∈ F × 2 } , θ N = 1 N ∑ n ≤ N ι n , α F , N = 1 N ∑ n ≤ N ι n D n , F . D_{n,F}=\mathbf{1}_{\{\operatorname{Disc}(f_n)\in F^{\times2}\}},\qquad
\theta_N=\frac{1}{N}\sum_{n\le N}\iota_n,\qquad
\alpha_{F,N}=\frac{1}{N}\sum_{n\le N}\iota_nD_{n,F}. D n , F = 1 { Disc ( f n ) ∈ F × 2 } , θ N = N 1 n ≤ N ∑ ι n , α F , N = N 1 n ≤ N ∑ ι n D n , F . The sums start at n = 1 n=1 n = 1 F × 2 F^{\times2} F × 2 α N = α Q , N \alpha_N=\alpha_{\mathbb{Q},N} α N = α Q , N
Proposition 7.2. For any fixed number field F F F F F F θ N \theta_N θ N α F , N \alpha_{F,N} α F , N θ , α \theta,\alpha θ , α
( S F ( f ) , A F ( f ) , O F ( f ) ) = ( θ − α , α , 1 − θ ) . (55) (S_F(f),A_F(f),O_F(f))=(\theta-\alpha,\alpha,1-\theta). \tag*{(55)} ( S F ( f ) , A F ( f ) , O F ( f )) = ( θ − α , α , 1 − θ ) . (55) Independently of the other limits, O F ( f ) O_F(f) O F ( f ) θ N \theta_N θ N
Proof. By Propositions 3.5 and 3.9 , for all sufficiently large n n n
1 { Gal F ( f n ) = S n } = ι n ( 1 − D n , F ) , 1 { Gal F ( f n ) = A n } = ι n D n , F . \mathbf{1}_{\{\operatorname{Gal}_F(f_n)=S_n\}}=\iota_n(1-D_{n,F}),\qquad
\mathbf{1}_{\{\operatorname{Gal}_F(f_n)=A_n\}}=\iota_nD_{n,F}. 1 { Gal F ( f n ) = S n } = ι n ( 1 − D n , F ) , 1 { Gal F ( f n ) = A n } = ι n D n , F . For a separable section, a subgroup containing A n A_n A n A n A_n A n S n S_n S n F F F ι n \iota_n ι n 1 − ι n 1-\iota_n 1 − ι n □ \square □
The criterion replaces full group determination by irreducibility, a modular factorization witness, and a square test. The existence of the resulting means still requires information about the family. At the endpoints, convergence can be tested by comparing pairs of containment indicators.
Corollary 7.3. Put H N = N − 2 ∑ 1 ≤ m , n ≤ N ∣ ι m − ι n ∣ H_N=N^{-2}\sum_{1\le m,n\le N}|\iota_m-\iota_n| H N = N − 2 ∑ 1 ≤ m , n ≤ N ∣ ι m − ι n ∣ F F F
O F ( f ) exists and lies in { 0 , 1 } ⟺ H N ⟶ 0. O_F(f)\text{ exists and lies in }\{0,1\}\quad\Longleftrightarrow\quad H_N\longrightarrow0. O F ( f ) exists and lies in { 0 , 1 } ⟺ H N ⟶ 0. Moreover, all three frequencies exist with O F ( f ) ∈ { 0 , 1 } O_F(f)\in\{0,1\} O F ( f ) ∈ { 0 , 1 } H N → 0 H_N\to0 H N → 0 α F , N \alpha_{F,N} α F , N
Proof. Counting unequal ordered pairs gives H N = 2 θ N ( 1 − θ N ) H_N = 2\theta_N(1-\theta_N) H N = 2 θ N ( 1 − θ N ) H N → 0 H_N \to0 H N → 0 θ N ∈ [ 0 , 1 / 4 ) ∪ ( 3 / 4 , 1 ] \theta_N \in[0,1/4) \cup(3/4,1] θ N ∈ [ 0 , 1/4 ) ∪ ( 3/4 , 1 ] ∣ θ N + 1 − θ N ∣ ≤ 1 / ( N + 1 ) |\theta_{N+1}-\theta_N| \le1/(N+1) ∣ θ N + 1 − θ N ∣ ≤ 1/ ( N + 1 ) Proposition 7.2 . □
In particular, if alternating containment holds in density one, then O F ( f ) = 0 O_F(f)=0 O F ( f ) = 0 F F F δ \delta δ ( 1 − δ , δ , 0 ) (1-\delta,\delta,0) ( 1 − δ , δ , 0 ) F F F F F F F F F F F F O F O_F O F F F F F F F
When the discriminant square class is a rational function on each of finitely many progressions, quantitative Hilbert irreducibility reduces its square values to the progressions on which that function is itself a square.
Proposition 7.4. Fix q ≥ 1 q \ge1 q ≥ 1
[ Disc ( f n ) ] = [ R r ( n ) ] ( n ≡ r ( m o d q ) ) , R r ( T ) ∈ Q ( T ) × , [\operatorname{Disc}(f_n)] = [R_r(n)] \quad(n \equiv r \pmod q), \qquad R_r(T) \in\mathbb{Q}(T)^\times, [ Disc ( f n )] = [ R r ( n )] ( n ≡ r ( mod q )) , R r ( T ) ∈ Q ( T ) × , where brackets denote rational square classes. Put I = { r m o d q : R r ∈ Q ( T ) × 2 } I=\{r \bmod q : R_r \in\mathbb{Q}(T)^{\times2}\} I = { r mod q : R r ∈ Q ( T ) × 2 }
α N − 1 N ∑ n ≤ N n m o d q ∈ I ι n ⟶ 0. \alpha_N-\frac{1}{N}\sum_{\substack{n\le N\\n\bmod q\in I}}\iota_n \longrightarrow0. α N − N 1 n ≤ N n mod q ∈ I ∑ ι n ⟶ 0. If alternating containment holds in density one, the triple over Q \mathbb{Q} Q ( 1 − ∣ I ∣ / q , ∣ I ∣ / q , 0 ) (1-|I|/q,|I|/q,0) ( 1 − ∣ I ∣/ q , ∣ I ∣/ q , 0 ) I I I A ( f ) = 0 A(f)=0 A ( f ) = 0
Proof. A square rational function has square values wherever defined and nonzero. Otherwise Y 2 − R r ( q T + r ) Y^2-R_r(qT+r) Y 2 − R r ( q T + r ) Q ( T ) \mathbb{Q}(T) Q ( T ) O ( N log N ) O(\sqrt{N}\log N) O ( N log N ) N N N [42 Theorem 3.4.4] . Summing over the finitely many classes and applying the indicator identities proves the result. □
Cluster sets and coefficient shifts
The prescription theorem reduces the frequency questions to the counting function of the set of symmetric degrees.
Corollary 7.6. For every 0 ≤ α ≤ β ≤ 1 0 \le\alpha\le\beta\le1 0 ≤ α ≤ β ≤ 1 ( s f ( N ) , a f ( N ) , o f ( N ) ) (s_f(N),a_f(N),o_f(N)) ( s f ( N ) , a f ( N ) , o f ( N ))
{ ( t , 0 , 1 − t ) : α ≤ t ≤ β } . (56) \{(t,0,1-t):\alpha\le t\le\beta\}. \tag*{(56)} {( t , 0 , 1 − t ) : α ≤ t ≤ β } . (56) For rational α , β \alpha,\beta α , β ( δ , 0 , 1 − δ ) (\delta,0,1-\delta) ( δ , 0 , 1 − δ ) 0 ≤ δ ≤ 1 0\le\delta\le1 0 ≤ δ ≤ 1
Proof. For the function associated with B B B N ≥ 3 N\ge3 N ≥ 3
s f ( N ) = # ( B ∩ [ 3 , N ] ) N , a f ( N ) = 0 , o f ( N ) = N − 2 N − s f ( N ) . (57) s_f(N)=\frac{\#(B\cap[3,N])}{N}, \qquad a_f(N)=0, \qquad o_f(N)=\frac{N-2}{N}-s_f(N). \tag*{(57)} s f ( N ) = N # ( B ∩ [ 3 , N ]) , a f ( N ) = 0 , o f ( N ) = N N − 2 − s f ( N ) . (57) Indeed, ( n − 1 ) ! < n ! / 2 (n-1)!<n!/2 ( n − 1 )! < n ! /2 n ≥ 3 n\ge3 n ≥ 3 S n \mathfrak{S}_n S n A n \mathfrak{A}_n A n
When α = β = δ \alpha=\beta=\delta α = β = δ
B = { n ≥ 3 : ∣ δ n ∣ − ∣ δ ( n − 1 ) ∣ = 1 } . B=\{n\ge3:|\delta n|-\lvert\delta(n-1)\rvert=1\}. B = { n ≥ 3 : ∣ δ n ∣ − ∣ δ ( n − 1 )∣ = 1 } . Its counting function is δ N + O ( 1 ) \delta N+O(1) δ N + O ( 1 ) α < β \alpha<\beta α < β Δ = β − α \Delta=\beta-\alpha Δ = β − α j ≥ 1 j\ge1 j ≥ 1 u j = β − Δ / ( j + 2 ) u_j=\beta-\Delta/(j+2) u j = β − Δ/ ( j + 2 )
then append zeros until that average is at most ℓ j = α + Δ / ( j + 2 ) \ell_j=\alpha+\Delta/(j+2) ℓ j = α + Δ/ ( j + 2 ) 0 < ℓ j < u j < 1 0<\ell_j<u_j<1 0 < ℓ j < u j < 1 1 / N 1/N 1/ N N N N α \alpha α β \beta β B B B (57) proves (56) .
For rational endpoints the construction decides membership in B B B α = β = 1 / 2 \alpha=\beta=1/2 α = β = 1/2 ( α , β ) = ( 0 , 1 ) (\alpha,\beta)=(0,1) ( α , β ) = ( 0 , 1 )
For r ≥ 1 r\geq1 r ≥ 1 d d d f [ r ] f^{[r]} f [ r ] f r , r + d f_{r,r+d} f r , r + d d ≥ 2 d\geq2 d ≥ 2
Joint linear disjointness gives a uniform bound on how many segment groups can change after extending the ground field.
Corollary 7.7. Fix a function from Theorem A. For every number field F F F f r , s f_{r,s} f r , s F F F Q \mathbb{Q} Q
⌊ log 2 [ F : Q ] ⌋ \left\lfloor\log_2 [F:\mathbb{Q}] \right\rfloor ⌊ log 2 [ F : Q ] ⌋ pairs ( r , s ) (r,s) ( r , s ) 0 ≤ r ≤ s − 2 0\leq r\leq s-2 0 ≤ r ≤ s − 2
Proof. Put D r , s = K r , s ∩ F D_{r,s}=K_{r,s}\cap F D r , s = K r , s ∩ F K r , s / Q K_{r,s}/\mathbb{Q} K r , s / Q F F F Gal ( K r , s / D r , s ) \operatorname{Gal}(K_{r,s}/D_{r,s}) Gal ( K r , s / D r , s ) D r , s D_{r,s} D r , s Q \mathbb{Q} Q I I I K r , s K_{r,s} K r , s D r , s D_{r,s} D r , s F F F
2 ∣ I ∣ ≤ ∏ ( r , s ) ∈ I [ D r , s : Q ] = [ ∏ ( r , s ) ∈ I D r , s : Q ] ≤ [ F : Q ] . 2^{|I|}\leq\prod_{(r,s)\in I}[D_{r,s}:\mathbb{Q}]
=\left[\prod_{(r,s)\in I}D_{r,s}:\mathbb{Q}\right]\leq[F:\mathbb{Q}]. 2 ∣ I ∣ ≤ ( r , s ) ∈ I ∏ [ D r , s : Q ] = ( r , s ) ∈ I ∏ D r , s : Q ≤ [ F : Q ] . This proves the bound. Only finitely many Taylor-polynomial groups change, so all the frequency conclusions are preserved.
Preserving finite initial data
The initial normalization a 0 = a 1 = 1 a_0=a_1=1 a 0 = a 1 = 1
Proposition 7.9. Let m ≥ 1 m\geq1 m ≥ 1 a 0 , … , a m ∈ Q > 0 a_0,\ldots,a_m\in\mathbb{Q}_{>0} a 0 , … , a m ∈ Q > 0 B ⊆ { m + 2 , m + 3 , … } B\subseteq\{m+2,m+3,\ldots\} B ⊆ { m + 2 , m + 3 , … } ε n > 0 \varepsilon_n>0 ε n > 0 n > m n>m n > m
f ( z ) = ∑ j = 0 m a j z j + ∑ n > m a n z n , a n ∈ Q > 0 , f(z)=\sum_{j=0}^{m}a_jz^j+\sum_{n>m}a_nz^n,\qquad a_n\in\mathbb{Q}_{>0}, f ( z ) = j = 0 ∑ m a j z j + n > m ∑ a n z n , a n ∈ Q > 0 , of order zero, with 0 < a n < min { ε n , 2 − n 2 } 0<a_n<\min\{\varepsilon_n,2^{-n^2}\} 0 < a n < min { ε n , 2 − n 2 } n > m n>m n > m (2) holds for every n ≥ m + 2 n\geq m+2 n ≥ m + 2
Gal ( K r , n / Q ) = S n − r ( n ≥ m + 2 , 1 ≤ r ≤ n − 2 ) . \operatorname{Gal}(K_{r,n}/\mathbb{Q})=\mathfrak{S}_{n-r}\qquad(n\geq m+2,\ 1\leq r\leq n-2). Gal ( K r , n / Q ) = S n − r ( n ≥ m + 2 , 1 ≤ r ≤ n − 2 ) . The whole family { K r , n : n ≥ m + 2 , 0 ≤ r ≤ n − 2 } \{K_{r,n}:n\geq m+2,\ 0\leq r\leq n-2\} { K r , n : n ≥ m + 2 , 0 ≤ r ≤ n − 2 } Q \mathbb{Q} Q
If the prefix satisfies a j 2 > 4 a j − 1 a j + 1 a_j^2>4a_{j-1}a_{j+1} a j 2 > 4 a j − 1 a j + 1 1 ≤ j < m 1\leq j<m 1 ≤ j < m j ≥ 1 j\geq1 j ≥ 1 B B B
Proof. For 0 ≤ r ≤ m 0 \le r \le m 0 ≤ r ≤ m g r , m + 1 ( X ) = ∑ j = r m a j X m + 1 − j g_{r,m+1}(X)=\sum_{j=r}^{m}a_jX^{m+1-j} g r , m + 1 ( X ) = ∑ j = r m a j X m + 1 − j a m + 1 = t > 0 a_{m+1}=t>0 a m + 1 = t > 0
g r , m + 2 ( X ) = X g r , m + 1 ( X ) + t X ( 0 ≤ r ≤ m ) g_{r,m+2}(X)=Xg_{r,m+1}(X)+tX \qquad(0\le r\le m) g r , m + 2 ( X ) = X g r , m + 1 ( X ) + tX ( 0 ≤ r ≤ m ) are Morse and have pairwise disjoint critical-value sets. The polynomials X g r , m + 1 Xg_{r,m+1} X g r , m + 1 Lemma 2.3 excludes only finitely many values of t t t g 0 , m + 1 + t g_{0,m+1}+t g 0 , m + 1 + t n = m + 2 n=m+2 n = m + 2 a r a_r a r a 0 a_0 a 0
At every new degree, the product specialization gives the asserted groups for all proper segments. Include the fixed extension and all preceding segment splitting fields in E E E log M f ( R ) = O ( ( log R ) 2 ) \log M_f(R)=O((\log R)^2) log M f ( R ) = O (( log R ) 2 ) a n < a n − 1 2 / ( 4 a n − 2 ) a_n<a_{n-1}^2/(4a_{n-2}) a n < a n − 1 2 / ( 4 a n − 2 ) a m + 1 a_{m+1} a m + 1 Lemma 2.6 then applies. The first coefficient t t t Lemma 2.3 ; subsequent coefficients are computable by Proposition 2.9 .
The extra degree in Proposition 7.9 is sometimes necessary. For a composite integer d ≥ 4 d\ge4 d ≥ 4
g d ( X ) = ( X + 1 ) d − 1. g_d(X)=(X+1)^d-1. g d ( X ) = ( X + 1 ) d − 1. For every parameter t t t g d ( X ) + t g_d(X)+t g d ( X ) + t Y d − ( 1 − t ) Y^d-(1-t) Y d − ( 1 − t ) Y ↦ Y a Y\mapsto Y^a Y ↦ Y a d = a b d=ab d = ab a , b > 1 a,b>1 a , b > 1 S d \mathfrak{S}_d S d
Preserving a sufficiently long prefix also gives approximation on any fixed disk, with an arbitrary frequency cluster set of the form (56) .
Corollary 7.10. Let Φ ( z ) = ∑ j ≥ 0 b j z j \Phi(z)=\sum_{j\ge0}b_jz^j Φ ( z ) = ∑ j ≥ 0 b j z j b j ∈ Q > 0 b_j\in\mathbb{Q}_{>0} b j ∈ Q > 0 R > 0 R>0 R > 0 ϵ > 0 \epsilon>0 ϵ > 0 0 ≤ α ≤ β ≤ 1 0\le\alpha\le\beta\le1 0 ≤ α ≤ β ≤ 1 f f f
max ∣ z ∣ ≤ R ∣ f ( z ) − Φ ( z ) ∣ < ϵ \max_{|z|\le R}|f(z)-\Phi(z)|<\epsilon ∣ z ∣ ≤ R max ∣ f ( z ) − Φ ( z ) ∣ < ϵ and the frequency-triple cluster set of f f f (56) . Any prescribed finite number of the initial coefficients of Φ \Phi Φ
Proof. Choose a sufficiently long Taylor polynomial of Φ \Phi Φ ∣ z ∣ ≤ R |z|\le R ∣ z ∣ ≤ R ϵ / 2 \epsilon/2 ϵ /2 ∑ n > m ϵ n R n < ϵ / 2 \sum_{n>m}\epsilon_nR^n<\epsilon/2 ∑ n > m ϵ n R n < ϵ /2 B B B α \alpha α β \beta β
Uniform computability and decision problems
We use the promise convention of Subsection 2.11. The inputs below are programs returning exact rational coefficients; the constructions always produce total programs satisfying the stated analytic and arithmetic promises. Uniformity in the prescribed set B B B
Proposition 7.12. There is no algorithm which, from a program computing the exact rational coefficients of a series, decides whether all three frequencies converge. This remains true under the promise of strictly positive coefficients and an entire function of order zero. Neither convergence nor nonconvergence is semidecidable under this promise.
Even under the additional promise that all three frequencies exist, the property O ( f ) ∈ { 0 , 1 } O(f) \in\{0,1\} O ( f ) ∈ { 0 , 1 }
Proof. Use the uniform algorithm of Proposition 2.9 with fixed computable bounds. Put M j = 2 2 j M_j=2^{2^j} M j = 2 2 j
B 0 = ⋃ j ≥ 0 ( [ M 2 j , M 2 j + 1 ) ∩ Z ≥ 3 ) . B_0=\bigcup_{j\geq0}\left([M_{2j},M_{2j+1})\cap\mathbb{Z}_{\geq3}\right). B 0 = j ≥ 0 ⋃ ( [ M 2 j , M 2 j + 1 ) ∩ Z ≥ 3 ) . This set is computable. Since M j + 1 / M j → ∞ M_{j+1}/M_j\to\infty M j + 1 / M j → ∞ e e e n ≥ 3 n\geq3 n ≥ 3 n n n B 0 B_0 B 0 n n n B e B_e B e e e e e e e e e e
For the second textbf, use all degrees until the machine halts and even degrees thereafter. The resulting triples are ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) ( 1 / 2 , 0 , 1 / 2 ) (1/2,0,1/2) ( 1/2 , 0 , 1/2 )
A real number is limit-computable , or Δ 2 0 \Delta^0_2 Δ 2 0 [ 0 , 1 ] [0,1] [ 0 , 1 ] [24 Theorem 2.21] . The prescription theorem transfers this description to Galois frequencies, while retaining its analytic and field-theoretic conclusions. For completeness, we include the elementary density construction.
Proposition 7.13. For δ ∈ [ 0 , 1 ] \delta\in[0,1] δ ∈ [ 0 , 1 ]
(i) δ \delta δ
(ii) δ = S ( f ) \delta=S(f) δ = S ( f )
(iii) there is a function satisfying every conclusion of Theorem A, with computable coefficients, whose triple is ( δ , 0 , 1 − δ ) (\delta,0,1-\delta) ( δ , 0 , 1 − δ )
Proof. Condition (iii) implies (ii). For (ii) implies (i), the exact label procedure following Proposition 2.9 computes each rational average s f ( N ) s_f(N) s f ( N ) q n ∈ [ 0 , 1 ] q_n\in[0,1] q n ∈ [ 0 , 1 ] δ \delta δ K 0 = 0 K_0=0 K 0 = 0
b n = 1 { K n − 1 < n q n } , K n = K n − 1 + b n . b_n=1_{\{K_{n-1}<nq_n\}},\qquad K_n=K_{n-1}+b_n. b n = 1 { K n − 1 < n q n } , K n = K n − 1 + b n . Then K n / n → δ K_n/n\to\delta K n / n → δ ε > 0 \varepsilon>0 ε > 0 l = max ( 0 , δ − ε ) l=\max(0,\delta-\varepsilon) l = max ( 0 , δ − ε ) u = min ( 1 , δ + ε ) u=\min(1,\delta+\varepsilon) u = min ( 1 , δ + ε ) n 0 n_0 n 0 l ≤ q n ≤ u l\leq q_n\leq u l ≤ q n ≤ u K ≥ 1 K\geq1 K ≥ 1 l n − K ≤ K n ≤ u n + K ln-K\leq K_n\leq un+K l n − K ≤ K n ≤ u n + K b n = 0 b_n=0 b n = 0 K n ≥ n q n ≥ l n K_n\geq nq_n\geq ln K n ≥ n q n ≥ l n b n = 1 b_n=1 b n = 1 K n < n q n + 1 ≤ u n + 1 K_n<nq_n+1\leq un+1 K n < n q n + 1 ≤ u n + 1 l ≤ 1 l\leq1 l ≤ 1 n n n ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 B = { n ≥ 3 : b n = 1 } B=\{n\geq3:b_n=1\} B = { n ≥ 3 : b n = 1 }
This gives an exact description of attainable limits on the edge A = 0 A=0 A = 0
Automatic Galois labels
Assume an automaton for the Galois labels λ ( n ) ∈ { S , A , O } \lambda(n)\in\{S,A,O\} λ ( n ) ∈ { S , A , O } [35 , 4 ] ; the following matrix version is convenient here.
Extend the labels arbitrarily to n = 0 , 1 , 2 n=0,1,2 n = 0 , 1 , 2 q ≥ 2 q\geq2 q ≥ 2 a a a q q q s 0 s_0 s 0 s 0 s_0 s 0 s s s
P i j = # { d ∈ { 0 , … , q − 1 } : δ ( i , d ) = j } q . P_{ij}=\frac{\#\{d\in\{0,\ldots,q-1\}:\delta(i,d)=j\}}{q}. P ij = q # { d ∈ { 0 , … , q − 1 } : δ ( i , d ) = j } . and let V V V s s s S , A , O S,A,O S , A , O e \mathbf{e} e s s s d = lcm ( 1 , … , s ) d=\operatorname{lcm}(1,\ldots,s) d = lcm ( 1 , … , s ) L = lim k → ∞ P d k L=\lim_{k\to\infty}P^{dk} L = lim k → ∞ P d k P P P d d d P d P^d P d P d P^d P d
Proposition 7.15. All three natural label frequencies exist if and only if every row of L V LV L V v v v L V LV L V
Proof. A prefix reaching state i i i a a a q k q^k q k [ a q k , ( a + 1 ) q k ) [aq^k,(a+1)q^k) [ a q k , ( a + 1 ) q k ) ( P k V ) i (P^kV)_i ( P k V ) i N v + o ( N ) Nv+o(N) N v + o ( N ) v v v [ 0 , q k ) [0,q^k) [ 0 , q k )
If L V = e v LV=\mathbf{e}v L V = e v P d k + t V → P t e v = e v P^{dk+t}V\to P^t\mathbf{e}v=\mathbf{e}v P d k + t V → P t e v = e v 0 ≤ t < d 0\leq t<d 0 ≤ t < d P k V P^kV P k V v v v [ 0 , N ) [0,N) [ 0 , N ) q q q q − 1 q-1 q − 1 K K K q K q^K q K q K q^K q K v v v K K K N N N
The endpoint condition says, respectively, that no reachable recurrent state has output O O O O = 0 O=0 O = 0 1 / 3 1/3 1/3 2 / 3 2/3 2/3 [4 ] . The prescribed-pattern theorem realizes this as the symmetric-degree set of an order-zero entire function.
Further questions
The prescription theorem and bounded-coefficient construction settle the universal convergence and zero-one assertions in the Katz–Rivin questions. A structural description of the series with convergent frequencies remains open. § 7 reduces the problem to two arithmetic means, while the undecidability results rule out a uniform algorithm on programs for arbitrary nonzero rational coefficients, and even for the existence of the other frequency over a fixed finite alphabet. Specific coefficient families can nevertheless admit precise answers, as Theorems B–E show.
Classical sections and smaller thresholds. Theorems D and E determine the central-binomial and Catalan groups in every degree. Sun’s additional bound n 2 + n + 5 n^2+n+5 n 2 + n + 5 x n P n ( 1 / x ) x^nP_n(1/x) x n P n ( 1/ x ) [45 ] , part (i). For general nonintegral binomial exponents, the degrees below the threshold remain to be classified uniformly in the parameter. It would also be useful to sharpen the bounds (25) and (A.5) and to obtain a two-cycle criterion adapted to these inertia elements without using the classification of finite simple groups. Another quantitative question is to make the implied constant in (6) numerical. An explicit containment threshold alone does not supply a numerical constant in the quadratic-large-sieve estimate.
The logarithmic discriminant. Yamamura’s conjecture asks for symmetry in every degree for 1 + x + x 2 / 2 + ⋯ + x n / n 1+x+x^2/2+\cdots+x^n/n 1 + x + x 2 /2 + ⋯ + x n / n ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) [13 ] for degrees n = m q n=mq n = m q m m m q q q p > n p>n p > n Proposition 6.11 .
Rational functions. Do all three frequencies converge for every rational function with nonzero Taylor coefficients? The examples in § 6 show that the other frequency need not be an endpoint. Even the class f ( x ) = P ( x ) / ( 1 − x ) f(x)=P(x)/(1-x) f ( x ) = P ( x ) / ( 1 − x ) n ≥ deg P n\geq\deg P n ≥ deg P P ( 1 ) ≠ 0 P(1)\ne0 P ( 1 ) = 0
( 1 − x ) f n ( x ) = P ( x ) − P ( 1 ) x n + 1 (1-x)f_n(x)=P(x)-P(1)x^{n+1} ( 1 − x ) f n ( x ) = P ( x ) − P ( 1 ) x n + 1 This connects the question to sparse polynomials with a growing exponent. The finite-alphabet construction varies the coefficients in long blocks and does not decide convergence for a fixed rational generating function.
Irreducible nonconvergence and alternating prescriptions. Can the frequencies fail to converge when every sufficiently large section is irreducible? Our nonconvergent examples obtain other degrees through rational or cyclotomic factors. An irreducible example would require compatible alternating groups or other proper transitive groups in a suitable collection of degrees; oscillation between symmetric and alternating groups would already suffice. More generally, can one prescribe alternating groups as well as symmetric and other groups in one Taylor sequence?
There is a concrete limitation to the one-parameter method in § 2 . If g ∈ Q [ X ] g\in\mathbb{Q}[X] g ∈ Q [ X ] n n n D ( T ) = Disc X ( g ( X ) + T ) D(T)=\operatorname{Disc}_X(g(X)+T) D ( T ) = Disc X ( g ( X ) + T ) n − 1 n-1 n − 1 Y 2 = D ( T ) Y^2=D(T) Y 2 = D ( T ) ⌊ ( n − 2 ) / 2 ⌋ \lfloor(n-2)/2\rfloor ⌊( n − 2 ) /2 ⌋ n ≥ 6 n\geq6 n ≥ 6 [17 ] therefore leaves only finitely many rational parameters with square discriminant. Thus, for a fixed Morse prefix, the argument cannot supply alternating specializations at arbitrarily small nonzero parameters. An alternating prescription may require additional parameters or a different generic group.
Explicit prime estimates
We give the explicit estimates used in Lemma 4.2 and then prove the smaller threshold for half-integral parameters. The argument first counts primes in one progression and then subtracts the primes for which a prescribed divisor divides the special index. We use φ \varphi φ
θ ( x ; q , a ) = ∑ p ≤ x p ≡ a ( m o d q ) log p . \theta(x;q,a)=\sum_{\substack{p\leq x\\p\equiv a\pmod q}}\log p. θ ( x ; q , a ) = p ≤ x p ≡ a ( mod q ) ∑ log p . The inputs are an explicit prime estimate in a fixed progression and the interval Brun–Titchmarsh inequality.
The general bound
Proof of Lemma 4.2 . We have
L ≥ max { 60 , Q } , 3 16 ≤ κ ≤ Q 8 . L\geq\max\{60,Q\},\qquad\frac{3}{16}\leq\kappa\leq\frac{Q}{8}. L ≥ max { 60 , Q } , 16 3 ≤ κ ≤ 8 Q . The explicit prime estimate of Bennett, Martin, O’Bryant, and Rechnitzer [5 Theorem 1.2 and equations (1.10)–(1.11)] gives, in a weakened form valid for every Q ≥ 3 Q\geq3 Q ≥ 3
∣ θ ( x ; Q , ρ ) − x φ ( Q ) ∣ < x 160 log x (58) \left|\theta(x;Q,\rho)-\frac{x}{\varphi(Q)}\right|<\frac{x}{160\log x} \tag*{(58)} θ ( x ; Q , ρ ) − φ ( Q ) x < 160 log x x (58) for x ≥ x 0 ( Q ) x \ge x_0(Q) x ≥ x 0 ( Q )
x 0 ( Q ) = { 8 ⋅ 10 9 , Q ≤ 10 5 , exp ( 0.03 Q log 3 Q ) , Q > 10 5 . x_0(Q) =
\begin{cases}
8 \cdot10^9, & Q \le10^5,\\
\exp(0.03\sqrt{Q}\log^3 Q), & Q > 10^5.
\end{cases} x 0 ( Q ) = { 8 ⋅ 1 0 9 , exp ( 0.03 Q log 3 Q ) , Q ≤ 1 0 5 , Q > 1 0 5 . Our lower bound on n n n U > x 0 ( Q ) U > x_0(Q) U > x 0 ( Q ) Q ≤ 10 5 Q \le10^5 Q ≤ 1 0 5 U > n ≥ e 60 U > n \ge e^{60} U > n ≥ e 60 Q > 10 5 Q > 10^5 Q > 1 0 5 ( log Q ) 3 / Q (\log Q)^3/\sqrt{Q} ( log Q ) 3 / Q
0.03 log 3 ( 10 5 ) 10 5 < 0.03 ⋅ 12 3 300 < 1 , \frac{0.03\log^3(10^5)}{\sqrt{10^5}} < \frac{0.03\cdot12^3}{300} < 1, 1 0 5 0.03 log 3 ( 1 0 5 ) < 300 0.03 ⋅ 1 2 3 < 1 , so $0.03\sqrt{Q}\log^3 Q < Q \le L$.
For L ≥ 60 L \ge60 L ≥ 60 Q ≤ L Q \le L Q ≤ L
log Q ≤ L / 10 , log ( 600 Q ) ≤ L / 4 , log ( 6 Q ) ≤ L / 8. (59) \log Q \le L/10,\qquad\log(600Q) \le L/4,\qquad\log(6Q) \le L/8. \tag*{(59)} log Q ≤ L /10 , log ( 600 Q ) ≤ L /4 , log ( 6 Q ) ≤ L /8. (59) Each follows by replacing Q Q Q L L L L = 60 L=60 L = 60 log U > L \log U > L log U > L log V ≤ L + log Q ≤ 11 L / 10 \log V \le L+\log Q \le11L/10 log V ≤ L + log Q ≤ 11 L /10 U + V = 13 W U+V=13W U + V = 13 W
∣ P ∣ ≥ θ ( V ; Q , ρ ) − θ ( U ; Q , ρ ) log V > W φ ( Q ) log V ( 1 − 13 φ ( Q ) 160 log U ) > 147 176 W φ ( Q ) L > 4 5 W φ ( Q ) L . \begin{aligned}
|\mathcal{P}| \ge\frac{\theta(V;Q,\rho)-\theta(U;Q,\rho)}{\log V} \\
&> \frac{W}{\varphi(Q)\log V}\left(1-\frac{13\varphi(Q)}{160\log U}\right) \\
&> \frac{147}{176}\frac{W}{\varphi(Q)L} > \frac{4}{5}\frac{W}{\varphi(Q)L}.
\end{aligned} ∣ P ∣ ≥ log V θ ( V ; Q , ρ ) − θ ( U ; Q , ρ ) > φ ( Q ) log V W ( 1 − 160 log U 13 φ ( Q ) ) > 176 147 φ ( Q ) L W > 5 4 φ ( Q ) L W . Here we used φ ( Q ) ≤ Q ≤ L \varphi(Q)\le Q\le L φ ( Q ) ≤ Q ≤ L
Put T = W / ( φ ( Q ) L ) T=W/(\varphi(Q)L) T = W / ( φ ( Q ) L ) d d d n n n a Q aQ a Q P \mathcal{P} P d ∣ j d\mid j d ∣ j Q Q Q q ∣ a q\mid a q ∣ a j j j c p cp c p ( c , a ) = 1 (c,a)=1 ( c , a ) = 1 p > ∣ a ∣ p>|a| p > ∣ a ∣ ( d , a Q ) = 1 (d,aQ)=1 ( d , a Q ) = 1 d ∣ j d\mid j d ∣ j Q d Qd Q d p ≡ a c − 1 ( m o d d ) p\equiv ac^{-1}\pmod d p ≡ a c − 1 ( mod d ) ( Q , d ) = 1 (Q,d)=1 ( Q , d ) = 1
For d = m ≤ n d=m\le\sqrt{n} d = m ≤ n ( m , a Q ) = 1 (m,aQ)=1 ( m , a Q ) = 1 [31 Theorem 2, equation (1.10)] therefore gives
# { p ∈ P : m ∣ j } ≤ 2 W φ ( Q ) φ ( m ) log ( W / ( Q m ) ) . (60) \#\{p\in\mathcal{P}:m\mid j\}\le\frac{2W}{\varphi(Q)\varphi(m)\log(W/(Qm))}. \tag*{(60)} # { p ∈ P : m ∣ j } ≤ φ ( Q ) φ ( m ) log ( W / ( Q m )) 2 W . (60) Here ( m , 6 ) = 1 (m,6)=1 ( m , 6 ) = 1 m ≥ 5 m\ge5 m ≥ 5 m ≤ 100 m\le100 m ≤ 100 φ ( m ) ≥ 4 \varphi(m)\ge4 φ ( m ) ≥ 4
log W Q m ≥ L − log 100 Q κ > L − log ( 600 Q ) ≥ 3 L 4 . \log\frac{W}{Qm}\ge L-\log\frac{100Q}{\kappa}>L-\log(600Q)\ge\frac{3L}{4}. log Q m W ≥ L − log κ 100 Q > L − log ( 600 Q ) ≥ 4 3 L . Thus (A.3) is at most 2 T / 3 2T/3 2 T /3 m > 100 m>100 m > 100 m m m φ ( m ) ≥ m > 10 \varphi(m)\ge\sqrt{m}>10 φ ( m ) ≥ m > 10 p e − 1 ( p − 1 ) ≥ p e / 2 p^{e-1}(p-1)\ge p^{e/2} p e − 1 ( p − 1 ) ≥ p e /2 m m m φ ( m ) \varphi(m) φ ( m ) 12 12 12
log W Q m ≥ L 2 − log Q κ ≥ L 2 − log ( 6 Q ) ≥ 3 L 8 . \log\frac{W}{Qm}\ge\frac{L}{2}-\log\frac{Q}{\kappa}\ge\frac{L}{2}-\log(6Q)\ge\frac{3L}{8}. log Q m W ≥ 2 L − log κ Q ≥ 2 L − log ( 6 Q ) ≥ 8 3 L . Hence (A.3) is at most 4 T / 9 4T/9 4 T /9 W > Q m W>Qm W > Q m
For d = r ≥ n d=r\ge\sqrt{n} d = r ≥ n
# { p ∈ P : r ∣ j } ≤ W Q r + 1. \#\{p\in\mathcal{P}:r\mid j\}\le\frac{W}{Qr}+1. # { p ∈ P : r ∣ j } ≤ Q r W + 1. Dividing by T T T Q / κ < 6 Q ≤ 6 L Q/\kappa<6Q\le6L Q / κ < 6 Q ≤ 6 L
L e − L / 2 + 6 L 2 e − L < 1 100 ( L ≥ 60 ) . Le^{-L/2}+6L^{2}e^{-L}<\frac{1}{100}\qquad(L\ge60). L e − L /2 + 6 L 2 e − L < 100 1 ( L ≥ 60 ) . Both terms decrease, and their values at 60 prove the inequality. Subtracting the two forbidden sets from (27) leaves more than
( 4 5 − 2 3 − 1 100 ) T = 37 300 T > T 10 \left(\frac{4}{5}-\frac{2}{3}-\frac{1}{100}\right)T=\frac{37}{300}T>\frac{T}{10} ( 5 4 − 3 2 − 100 1 ) T = 300 37 T > 10 T primes. Finally,
T 10 n = κ n 10 φ ( Q ) L ≥ 3 e L / 2 160 L 2 > 1. \frac{T}{10\sqrt{n}}=\frac{\kappa\sqrt{n}}{10\varphi(Q)L}\ge\frac{3e^{L/2}}{160L^{2}}>1. 10 n T = 10 φ ( Q ) L κ n ≥ 160 L 2 3 e L /2 > 1. The last expression increases for L ≥ 60 L\ge60 L ≥ 60 e 30 > 2 30 e^{30}>2^{30} e 30 > 2 30 b / c ≥ 3 / 2 b/c\ge3/2 b / c ≥ 3/2 p > U ≥ 9 n / 8 > n + C p>U\ge9n/8>n+C p > U ≥ 9 n /8 > n + C p > R F p>R_F p > R F p > ∣ a ∣ , b p>|a|,b p > ∣ a ∣ , b n ≥ 100 ∣ a ∣ n\ge100|a| n ≥ 100∣ a ∣ ∣ a ∣ / b ≤ n / 200 |a|/b\le n/200 ∣ a ∣/ b ≤ n /200
3 n 4 − n 200 < j ≤ 7 n 8 + n 200 . \frac{3n}{4}-\frac{n}{200}<j\le\frac{7n}{8}+\frac{n}{200}. 4 3 n − 200 n < j ≤ 8 7 n + 200 n . These inequalities imply all the asserted bounds on j j j
The half-integral case
For an odd integer a a a ρ = ρ ( a ) \rho=\rho(a) ρ = ρ ( a )
ρ ≡ a + 2 ( m o d 4 ) , ρ ≡ { − a ( m o d 3 ) , 3 ∤ a , 1 ( m o d 3 ) , 3 ∣ a . \rho\equiv a+2\pmod4,\qquad
\rho\equiv
\begin{cases}
-a\pmod3,&3\nmid a,\\
1\pmod3,&3\mid a.
\end{cases} ρ ≡ a + 2 ( mod 4 ) , ρ ≡ { − a ( mod 3 ) , 1 ( mod 3 ) , 3 ∤ a , 3 ∣ a . Then ( p − a ) / 2 (p-a)/2 ( p − a ) /2 p ≡ ρ ( m o d 12 ) p\equiv\rho\pmod{12} p ≡ ρ ( mod 12 ) a = 1 a=1 a = 1 (25) .
Lemma A.3. Let n ≥ 10 6 n\ge10^{6} n ≥ 1 0 6 a a a ∣ a ∣ ≤ n / 100 |a|\le n/100 ∣ a ∣ ≤ n /100
P = { p prime : 3 n / 2 < p ≤ 7 n / 4 , p ≡ ρ ( a ) ( m o d 12 ) } . \mathcal{P}=\{p\ \text{prime}:3n/2<p\le7n/4,\ p\equiv\rho(a)\pmod{12}\}. P = { p prime : 3 n /2 < p ≤ 7 n /4 , p ≡ ρ ( a ) ( mod 12 )} . Then
∣ P ∣ > 547 n 10000 log n > 2. |\mathcal{P}|>\frac{547n}{10000\log n}>2. ∣ P ∣ > 10000 log n 547 n > 2. For every factorization n = m r n=mr n = m r 2 ≤ m ≤ r 2\le m\le r 2 ≤ m ≤ r p ∈ P p\in\mathcal{P} p ∈ P
m ∤ ( p − a ) / 2 and r ∤ ( p − a ) / 2. m\nmid(p-a)/2\qquad\text{and}\qquad r\nmid(p-a)/2. m ∤ ( p − a ) /2 and r ∤ ( p − a ) /2. Proof. Write L = log n > 13.8 L=\log n>13.8 L = log n > 13.8 U = 3 n / 2 U=3n/2 U = 3 n /2 V = 7 n / 4 V=7n/4 V = 7 n /4 [37 Theorems 1 and 2, p. 398] give
max 1 ≤ y ≤ x ∣ θ ( y ; 12 , ρ ) − y 4 ∣ ≤ { 2.072 x , x ≤ 10 10 , 0.004560 x / 4 , x ≥ 10 10 . \max_{1\le y\le x}\left|\theta(y;12,\rho)-\frac{y}{4}\right|
\le
\begin{cases}
2.072\sqrt{x},&x\le10^{10},\\
0.004560x/4,&x\ge10^{10}.
\end{cases} 1 ≤ y ≤ x max θ ( y ; 12 , ρ ) − 4 y ≤ { 2.072 x , 0.004560 x /4 , x ≤ 1 0 10 , x ≥ 1 0 10 . Apply this maximum bound with the common endpoint V V V 10 10 10^{10} 1 0 10 4.144 7 / 4 < 5.5 4.144\sqrt{7/4}<5.5 4.144 7/4 < 5.5
θ ( V ; 12 , ρ ) − θ ( U ; 12 , ρ ) n ≥ { 1 / 16 − 5.5 / n , V ≤ 10 10 , 1 / 16 − 0.003990 , V ≥ 10 10 . \frac{\theta(V;12,\rho)-\theta(U;12,\rho)}{n}
\ge
\begin{cases}
1/16-5.5/\sqrt{n},&V\le10^{10},\\
1/16-0.003990,&V\ge10^{10}.
\end{cases} n θ ( V ; 12 , ρ ) − θ ( U ; 12 , ρ ) ≥ { 1/16 − 5.5/ n , 1/16 − 0.003990 , V ≤ 1 0 10 , V ≥ 1 0 10 . Both lower bounds are at least 0.057 for n ≥ 10 6 n\ge10^{6} n ≥ 1 0 6 log ( 7 / 4 ) < 0.56 \log(7/4)<0.56 log ( 7/4 ) < 0.56
∣ P ∣ ≥ 0.057 n log V > n L 0.057 13.8 13.8 + 0.56 = n L 57 1000 345 359 > 547 n 10000 L . |\mathcal{P}|\ge\frac{0.057n}{\log V}>\frac{n}{L}0.057\frac{13.8}{13.8+0.56}
=\frac{n}{L}\frac{57}{1000}\frac{345}{359}>\frac{547n}{10000L}. ∣ P ∣ ≥ log V 0.057 n > L n 0.057 13.8 + 0.56 13.8 = L n 1000 57 359 345 > 10000 L 547 n . Put j = ( p − a ) / 2 j=(p-a)/2 j = ( p − a ) /2 d d d 6 a 6a 6 a p ∈ P p\in\mathcal{P} p ∈ P d ∣ j d\mid j d ∣ j ( j , 6 ) = 1 (j,6)=1 ( j , 6 ) = 1 q ∣ a , d q\mid a,d q ∣ a , d d ∣ j d\mid j d ∣ j
imply q ∣ p q \mid p q ∣ p q ≤ ∣ a ∣ < p q \leq|a| < p q ≤ ∣ a ∣ < p ( d , 6 a ) = 1 (d,6a)=1 ( d , 6 a ) = 1 d ∣ j d \mid j d ∣ j 12 d 12d 12 d p p p
It remains to consider ( d , 6 a ) = 1 (d,6a)=1 ( d , 6 a ) = 1 d = m ≤ n d=m\leq\sqrt{n} d = m ≤ n [31 Theorem 2, equation (1.10)] gives
# { p ∈ P : m ∣ j } ≤ n 8 φ ( m ) log ( n / ( 48 m ) ) . (61) \#\{p\in\mathcal{P}:m\mid j\}\leq\frac{n}{8\varphi(m)\log(n/(48m))}. \tag*{(61)} # { p ∈ P : m ∣ j } ≤ 8 φ ( m ) log ( n / ( 48 m )) n . (61) Its hypothesis 12 m < n / 4 12m<n/4 12 m < n /4 n > 48 \sqrt{n}>48 n > 48 ( m , 6 ) = 1 (m,6)=1 ( m , 6 ) = 1 m = 5 m=5 m = 5 m ≥ 7 m\geq7 m ≥ 7 m = 5 m=5 m = 5
n 32 log ( n / 240 ) < 0.052 n L , \frac{n}{32\log(n/240)}<\frac{0.052n}{L}, 32 log ( n /240 ) n < L 0.052 n , because log 240 < 5.49 \log240<5.49 log 240 < 5.49 13.8 / [ 32 ( 13.8 − 5.49 ) ] < 0.052 13.8/[32(13.8-5.49)]<0.052 13.8/ [ 32 ( 13.8 − 5.49 )] < 0.052 7 ≤ m ≤ 100 7\leq m\leq100 7 ≤ m ≤ 100 φ ( m ) ≥ 6 \varphi(m)\geq6 φ ( m ) ≥ 6
n 48 log ( n / 4800 ) < 0.0541 n L , \frac{n}{48\log(n/4800)}<\frac{0.0541n}{L}, 48 log ( n /4800 ) n < L 0.0541 n , using log 4800 < 8.48 \log4800<8.48 log 4800 < 8.48 13.8 / [ 48 ( 13.8 − 8.48 ) ] < 0.0541 13.8/[48(13.8-8.48)]<0.0541 13.8/ [ 48 ( 13.8 − 8.48 )] < 0.0541 m > 100 m>100 m > 100 m m m φ ( m ) ≥ m > 10 \varphi(m)\geq\sqrt{m}>10 φ ( m ) ≥ m > 10 φ ( m ) \varphi(m) φ ( m )
n 96 ( 1 2 L − log 48 ) < 0.048 n L , \frac{n}{96(\frac{1}{2}L-\log48)}<\frac{0.048n}{L}, 96 ( 2 1 L − log 48 ) n < L 0.048 n , using log 48 < 3.88 \log48<3.88 log 48 < 3.88 13.8 / [ 96 ( 6.9 − 3.88 ) ] < 0.048 13.8/[96(6.9-3.88)]<0.048 13.8/ [ 96 ( 6.9 − 3.88 )] < 0.048
For d = r ≥ n d=r\geq\sqrt{n} d = r ≥ n
# { p ∈ P : r ∣ j } ≤ n 48 r + 1 ≤ n 48 + 1 < 0.00031 n L . \#\{p\in\mathcal{P}:r\mid j\}\leq\frac{n}{48r}+1\leq\frac{\sqrt{n}}{48}+1<\frac{0.00031n}{L}. # { p ∈ P : r ∣ j } ≤ 48 r n + 1 ≤ 48 n + 1 < L 0.00031 n . The last inequality holds at n = 10 6 n=10^{6} n = 1 0 6
L 48 n + L n < 14 48 ⋅ 1000 + 14 10 6 < 0.00031 , \frac{L}{48\sqrt{n}}+\frac{L}{n}<\frac{14}{48\cdot1000}+\frac{14}{10^{6}}<0.00031, 48 n L + n L < 48 ⋅ 1000 14 + 1 0 6 14 < 0.00031 , and the left side decreases thereafter. The union of the two excluded sets therefore has fewer than ( 0.0541 + 0.00031 ) n / L < 0.0547 n / L (0.0541+0.00031)n/L<0.0547n/L ( 0.0541 + 0.00031 ) n / L < 0.0547 n / L ∣ P ∣ |\mathcal{P}| ∣ P ∣
The preceding estimate gives the following smaller threshold when b = 2 b=2 b = 2
N 2 ( a , C , F ) = ⌈ max { 10 6 , 100 ∣ a ∣ , 2 C , R F } ⌉ . (62) N_2(a,C,F)=\left\lceil\max\{10^{6},100|a|,2C,R_F\}\right\rceil. \tag*{(62)} N 2 ( a , C , F ) = ⌈ max { 1 0 6 , 100∣ a ∣ , 2 C , R F } ⌉ . (62) where a a a R F R_F R F F F F R F = 1 R_F=1 R F = 1 P \mathcal{P} P n + C n+C n + C R F R_F R F j = ( p − a ) / 2 j=(p-a)/2 j = ( p − a ) /2
7 n / 10 < j < 9 n / 10 , n < n − j < n / 2. 7n/10<j<9n/10,\qquad\sqrt{n}<n-j<n/2. 7 n /10 < j < 9 n /10 , n < n − j < n /2. The local factors are tame and have degrees j j j n − j n-j n − j n = m r n=mr n = m r j j j C = 0 C=0 C = 0 s = a / 2 s=a/2 s = a /2
Polynomial weights
For Corollary 4.8 , suppose the nonzero coefficients agree for all i ≥ J i \ge J i ≥ J
a i = P ( i ) ( s + i ) ( i ! ) r , s = a / b , r ∈ Z ≥ 0 , P ( − s ) ≠ 0. a_i = \frac{P(i)}{(s+i)(i!)^r}, \qquad s = a/b,\quad r \in\mathbb{Z}_{\ge0},\quad P(-s) \ne0. a i = ( s + i ) ( i ! ) r P ( i ) , s = a / b , r ∈ Z ≥ 0 , P ( − s ) = 0. Write P = A / D P=A/D P = A / D A ∈ Z [ T ] A \in\mathbb{Z}[T] A ∈ Z [ T ] D D D
d = deg A , h = max i ∣ [ T i ] A ∣ , K = b d A ( − a / b ) ∈ Z ∖ { 0 } . d=\deg A,\qquad h=\max_i |[T^i]A|,\qquad K=b^d A(-a/b)\in\mathbb{Z}\setminus\{0\}. d = deg A , h = i max ∣ [ T i ] A ∣ , K = b d A ( − a / b ) ∈ Z ∖ { 0 } . Write each modified coefficient a i = m i / ℓ i a_i=m_i/\ell_i a i = m i / ℓ i 0 ≤ i < J 0\le i<J 0 ≤ i < J ℓ i > 0 \ell_i>0 ℓ i > 0 (25) , take C = 0 C=0 C = 0 H H H
J , D , ∣ K ∣ , ( d + 2 ) 2 , ( d + 1 ) h , max 0 ≤ i < J { ∣ m i ∣ , ℓ i } , J,\ D,\ |K|,\ (d+2)^2,\ (d+1)h,\ \max_{0\le i<J}\{|m_i|,\ell_i\}, J , D , ∣ K ∣ , ( d + 2 ) 2 , ( d + 1 ) h , 0 ≤ i < J max { ∣ m i ∣ , ℓ i } , where the last maximum is omitted if J = 0 J=0 J = 0 F F F n n n
Indeed the special index j j j j j j p p p H H H A ( 0 ) A(0) A ( 0 ) j j j A ( j ) ≡ A ( − a / b ) ≢ 0 ( m o d p ) A(j)\equiv A(-a/b)\not\equiv0\pmod p A ( j ) ≡ A ( − a / b ) ≡ 0 ( mod p ) p > ∣ K ∣ p>|K| p > ∣ K ∣ − 1 -1 − 1 A ( n ) A(n) A ( n )
0 < ∣ A ( n ) ∣ ≤ ( d + 1 ) h n d ≤ n d + 1 , 0<|A(n)|\le(d+1)hn^d\le n^{d+1}, 0 < ∣ A ( n ) ∣ ≤ ( d + 1 ) h n d ≤ n d + 1 , at most d d d n n n A ( n ) A(n) A ( n ) n ≥ 10 ( d + 2 ) \sqrt n\ge10(d+2) n ≥ 10 ( d + 2 ) Lemma 4.2 . Thus at least two primes remain for irreducibility, and at least one remains for every factor pair, including the square-degree pair used in Müller’s theorem. The same group proof applies. No extra dependence on r r r p > n p>n p > n i ! i! i ! p p p
