Jul 17, 2017 - ANDREW FIORI AND ANDREW SHALLUE. Abstract. ...... [Lan02] Serge Lang, Algebra, third ed., Graduate Texts in Mathematics, vol. 211 ...

0 downloads 2 Views 252KB Size

arXiv:1707.05002v1 [math.NT] 17 Jul 2017

ANDREW FIORI AND ANDREW SHALLUE Abstract. In this paper we obtain lower and upper bounds on the average number of liars for the Quadratic Frobenius Pseudoprime Test of Grantham [Gra01], generalizing arguments of Erd˝ os and Pomerance [EP86] and Monier [Mon80]. These bounds are provided for both Jacobi symbol ±1 cases, providing evidence for the existence of several challenge pseudoprimes.

1. Introduction A pseudoprime is a composite number that satisfies some necessary condition for primality. Since primes are necessary building blocks for so many algorithms, and since the most common way to find primes in practice is to apply primality testing algorithms based on such necessary conditions, it is important to gather what information we can about pseudoprimes. In addition to the practical benefits, pseudoprimes have remarkable divisibility properties that make them fascinating objects of study. The most common necessary condition used in practice is that the number has no small divisors. Another common necessary condition follows from a theorem of Fermat, that if n is prime and gcd(a, n) = 1 then an−1 = 1 (mod n). We denote by F (n) the set of Fermat liars with respect to n. For the purposes of generalization, it is useful to translate the Fermat condition to polynomial rings. Let n be prime, let R = Z/nZ, assume a ∈ R× , and construct the polynomial ring R[x]/hx−ai. Then a little work shows that xn = x in R[x]/hx − ai [Gra01, Proof of Theorem 4.1]. After all, x = a in R[x]/hx − ai, we have R[x]/hx − ai ∼ = R as fields, and an = a in R. The advantage of this view is that x − a may be replaced by an arbitrary polynomial. Definition 1 ([Gra01]). Let f (x) ∈ Z[x] be a monic polynomial of degree d and discriminant ∆. Then composite n is a Frobenius pseudoprime with respect to f (x) if the following conditions all hold. (1) (Integer Divisibility) We have gcd(n, f (0)∆) = 1. i (2) (Factorization) Let f0 (x) = f (x) (mod n). Define Fi (x) = gcmd(xn − x, fi−1 (x)) and fi (x) = fi−1 (x)/Fi (x) for 1 ≤ i ≤ d. All of the gcmds exist and fd (x) = 1. (3) (Frobenius) For 2 ≤Pi ≤ d, Fi (x) | Fi (xn ). S (4) (Jacobi) Let S = 2|i deg(Fi (x))/i. Have (−1) = (∆ | n), where (∆ | n) is the Jacobi symbol. Here gcmd stands for “greatest common monic divisor” [Gra01]. If g1 (x), g2 (x), f (x) are all monic and gcmd(g1 (x), g2 (x)) = f (x) with respect to n this means that the ideal generated by g1 (x), g2 (x) equals the ideal generated by f (x) in (Z/nZ)[x]. The gcmd may not exist, but when it does it is unique. Grantham shows that if gcmd(g1 (x), g2 (x)) exists in (Z/nZ)[x], then for all primes p | n, gcd(g1 (x), g2 (x)) has the same degree when taken over Z/pZ [Gra01, Corollary 3.3]. Furthermore, the Euclidean algorithm when applied to g1 (x), g2 (x) will either correctly compute their gcmd, or find a proper factor of n [Gra01, Proposition 3.5]. 2000 Mathematics Subject Classification. Primary 11Y11; Secondary 11A41. Key words and phrases. Primality Testing, Pseudoprime, Frobenius Pseudoprime, Lucas Pseudoprime. A.F. gratefully acknowledges support from the Pacific Institute for Mathematical Sciences (PIMS). A.S. supported by an Artistic and Scholarly Development grant from Illinois Wesleyan University. 1

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

2

Example. Suppose d = 1 and n is a Frobenius pseudoprime with respect to f (x) = x − a. Then gcmd(xn − x, x − a) = x − a, which means an = a (mod n), and hence a is a Fermat liar with respect to n. Conversely, if a is a Fermat liar then gcd(a, n) = 1 and gcmd(xn − x, x − a) = x − a, from which we conclude that n is a Frobenius pseudoprime with respect to x − a. We denote by Ld (n) the set of Frobenius liars of degree d with respect to n, and note by the − example above that L1 (n) = F (n). We will further divide the set L2 (n) into L+ 2 (n) and L2 (n). A − degree 2 polynomial f (x) with discriminant ∆ will be in L+ 2 (n) (respectively L2 (n)) if (∆ | n) = 1 (respectively −1). Notice that if (∆ | n) = 0, f (x) is not a liar since it fails the Integer Divisibility step. Let Frob2 (y, f (x)) be the set of degree-2 Frobenius pseudoprimes with respect to f (x), up to bound y, and similarly divide them into + and − sets according to the Jacobi symbol. Further, let Frob2 (f (x)) be the (possibly infinite) set of all such pseudoprimes. By abuse of notation, the same symbols will be used for the size of each set. The main goal of this work is to generalize [EP86], which bounds the average number of Fermat liars, strong liars, and Euler liars. We prove the following two theorems. Theorem 1. For all α satisfying Proposition 19, in particular α ≤ 23 8 , we have X −1 3 −1+o(1) y 3−α −o(1) < L+ 2 (n) < y · L(y) n≤y

where the sum is restricted to composite n. Moreover, the same bounds hold if we replace L+ 2 (n) by L2 (n). Here L(y) = exp((log y)(log log log y)/ log log y), with log being the natural logarithm. Theorem 2. For all α satisfying Proposition 20, in particular α ≤ 34 , we have X −1 3 −1+o(1) y 3−α −o(1) < L− 2 (n) < y · L(y) n≤y

where the sum is restricted to composite n.

1 As a comparison, if n is prime then the size of L2 (n) is (n − 1)2 , L+ 2 (n) = 2 (n − 1)(n − 2), and 1 L− 2 (n) = 2 n(n − 1). Thus the average count of liars for composites is rather large.

Remark 3. We obtain the same results if we restrict to odd composite n, or more generally if we restrict to composite n coprime to some fixed value. These theorems count pairs (f (x), n) where n ≤ y and n is a degree-2 Frobenius pseudoprime with respect to f (x). We thus have the following corollary on the average count of degree-2 Frobenius pseudoprimes with Jacobi symbol −1. Corollary 4. Suppose α satisfies the conditions outlined in Theorem 2. Then 1 X 2 1−α−1 −o(1) Frob− . 2 (y, x + ax + b) ≥ y 2 y a,b≤y

In [Gra01], Grantham offers $6.20 for exhibiting a Frobenius pseudoprime with respect to x2 + 5x+5 that is congruent to 2 or 3 modulo 5. The proper generalization for these Grantham challenge − 2 pseudoprimes are the sets Frob2 (x + ax + b), since the condition of being 2, 3 mod 5 is equivalent 2 to ∆(x + 5x + 5) | n = −1. By Corollary 4 these sets are infinite on average, providing good evidence that there are infinitely many Grantham challenge pseudoprimes. Further motivation for the present work comes from other challenge pseudoprimes. Pomerance, Selfridge, and Wagstaff ask in [PSW80] whether there exists composite n that is simultaneously a base-2 Fermat pseudoprime, a Fibonacci pseudoprime, and congruent to 2 or 3 modulo 5. Potentially even more rare are Baillie pseudoprimes [BW80] (or Baillie-PSW pseudoprimes), which ask for composite n that are simultaneously base-2 strong pseudoprimes and strong Lucas pseudoprimes with respect to a polynomial x2 − P x + Q chosen in a prescribed way to ensure that

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

3

P 2 − 4Q | n = −1. Though it is not clear in either case whether the conditions correspond to Frobenius pseudoprimes or strong Frobenius pseudoprimes to a single polynomial f (x), quadratic Frobenius pseudoprimes provide a natural generalization of the types of conditions requested. From this we conclude that the division of P L2 (n)− into (∆ | n) = ±1 cases is of fundamental importance, and in particular that bounding n≤y L2 (n) is of strong interest. Though not explored in this work, since Frob2 (x2 − P x + Q) is a subset of the set of (P, Q)Lucas pseudoprimes [Gra01, Theorem 4.9], there are potential applications to the theory of Lucas pseudoprimes.

2. Degree-2 Frobenius pseudoprimes This work focuses on the degree 2 case. We reproduce the definition and give some basic facts about Frobenius pseudoprimes and liars. Definition 2. Let f (x) ∈ Z[x] be a degree 2 monic polynomial with discriminant ∆, and let n be composite. Then n is a degree-2 Frobenius pseudoprime with respect to f (x) if the following four conditions hold. (1) (Integer Divisibility) We have gcd(n, f (0)∆) = 1. 2 (2) (Factorization) Let F1 (x) = gcmd(xn − x, f (x)), f1 (x) = f (x)/F1 (x), F2 (x) = gcmd(xn − x, f1 (x)), and f2 (x) = f1 (x)/F2 (x). All these polynomials exist and f2 (x) = 1. (3) (Frobenius) We have F2 (x) | F2 (xn ). (4) (Jacobi) We have (−1)S = (∆ | n), where S = deg(F2 (x))/2.

Alternatively, in this case we call f (x) a degree-2 Frobenius liar with respect to n.

The first condition ensures that ∆ 6= 0 and 0 is not a root of f (x). Since the discriminant is nonzero, f (x) is squarefree. Thus the roots of f (x) are nonzero and distinct. Example. Consider f (x) = x2 − 1 with ∆ = 4. If n is odd, F1 (x) = f (x) and F2 (x) = 1, so the Frobenius step is trivially satisfied. Since S = 0, n will be a Frobenius pseudoprime as long as (∆ | n) = 1. Since 4 is a square modulo n for all n ≥ 5, we conclude that all odd n ≥ 5 have at least one degree-2 Frobenius liar. Example. Next consider f (x) = x2 + 1 with ∆ = −4. Observe that n = 1 (mod 4) if and only if (−1)(n−1)/2 = 1, which is true if and only if gcmd(xn − x, f (x)) 6= 1. In this case F2 (x) = 1 and S = 1 = (−1 | n) = (∆ | n). In the other case, n = 3 (mod 4) if and only if gcmd(xn − x, f (x)) = 1. 2 2 However, (−1)(n −1)/2 = 1 and so gcmd(xn − x, f (x)) = f (x). For the Frobenius step, we know x2 + 1 | x2n + 1 since if a is a root of x2 + 1, n odd implies that (a2 )n = −1 and hence a is also a root of x2n + 1. Finally, the Jacobi step is satisfied since S = −1 = (∆ | n). This demonstrates that x2 + 1 is also a liar for all odd composite n. The minimum number of degree-2 Frobenius liars for odd composite n is in fact 2, first achieved by n = 15. If we fix n and instead restrict to liars with (∆ | n) = −1 then it is possible that no such liars exist. See Section 3.4 for a more in depth discussion of this case. Q We next give several reinterpretations of the conditions under which a number n = i pri i is a degree-2 Frobenius pseudoprime with respect to a polynomial f . We treat cases (∆ | n) = +1 and (∆ | n) = −1 separately. 2.1. The case (∆ | n) = +1. Supposing we already know that (∆ | n) = +1, n is a degree-2 Frobenius pseudoprime with respect to f (x) if and only if (1) (Integer Divisibility) we have gcd(n, f (0)∆) = 1, and (2) (Factorization) gcmd(xn − x, f (x)) = f (x) (mod n).

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

4

All other conditions follow immediately. In particular, because f (x) | xn − x modulo n, it is not possible for the Euclidean algorithm to discover any non-trivial factors of n. We observe that these conditions can be interpreted locally, giving us the following result. Q Proposition 5. Positive integer n = i pri i satisfies Definition 2 in the case (∆ | n) = 1 if and only if (1) (Integer Divisibility) ∆ is a unit modulo n and 0 is not a root of f (x) modulo pi for all i, and (2) (Factorization) gcmd(xn − x, f (x)) = f (x) (mod pri i ) for all i. Proof. First assume that n is a degree-2 Frobenius pseudoprime with respect to f (x) according to Definition 2 and that (∆ | n) = 1. Then gcd(n, f (0)∆) = 1, so gcd(∆, n) = 1 making ∆ a unit, and gcd(f (0), n) = 1. It follows that f (0) 6= 0 (mod p) for all p | n. The Jacobi condition in Definition 2 along with the assumption that (∆ | n) = 1 ensures S = 0 and so deg(F2 (x)) = 0. All the polynomials in condition (2) are monic, so F2 (x) = 1, which implies f1 (x) = 1, so that gcmd(xn − x, f (x)) = f (x). Since this identity is true modulo n, it is true modulo pri i for all i. Conversely, if gcmd(xn − x, f (x)) = f (x) (mod pri i ) for all i, then the identity is true modulo n by the Chinese remainder theorem. It follows that f1 (x) = 1 and so F2 (x) = 1. Thus condition (2) of Definition 2 is true, condition (3) follows trivially, and condition (4) is true since S = 0. We are assuming that ∆ is a unit modulo n, from which it follows that gcd(∆, n) = 1. Furthermore, f (0) 6= 0 (mod p) for all p | n implies gcd(f (0), n) = 1. Thus condition (1) is satisfied. 2.2. The Case (∆ | n) = −1. When (∆ | n) = −1 we need a couple more conditions. Q Proposition 6. Positive integer n = i pri i satisfies Definition 2 in the case (∆ | n) = −1 if and only if it satisfies the following conditions: (1) (Integer Divisibility) discriminant ∆ is a unit modulo n and 0 is not a root of f (x) (mod pi ) for all i, (2) (Factorization 1) gcmd(xn − x, f (x)) = 1 (mod pri i ) for all i, 2 (3) (Factorization 2) gcmd(xn − x, f (x)) = f (x) (mod pri i ) for all i, (4) (Frobenius) if α is a root of f (x) modulo pri i , then so too is αn for all i. 2

In particular, these conditions are sufficient to ensure that gcmd(xn − x, f (x)) and gcmd(xn − x, f (x)) exist modulo n. Proof. Following the argument from Proposition 5, condition (1) from Definition 2 holds if and only if ∆ is a unit modulo n and 0 is not a root of f (x) (mod pi ) for all i. Now, if we assume n satisfies Definition 2, then by condition (4) we must have S = 1 and 2 hence deg(F2 (x)) = 2. Thus gcmd(xn − x, f1 (x)) = f (x), and since f2 (x) = 1 we further have f1 (x) = f (x). This is only possible if gcmd(xn − x, f (x)) = 1. Since these identities hold modulo n, they hold modulo pri i for all i. Finally, F2 (x) | F2 (xn ) means f (x) | f (xn ) (mod n) and hence that αn is a root of f (x) modulo pri i whenever α is. Conversely, assume n satisfies conditions (2), (3), (4) from the statement of the proposition. By the Chinese remainder theorem, conditions (2) and (3) mean that gcmd(xn − x, f (x)) = 1 (mod n) 2 and gcmd(xn − x, f (x)) = f (x) (mod n). In the language of Definition 2, we have F1 (x) = 1, F2 (x) = f (x), and f2 (x) = 1 as required. It follows that the Jacobi step is satisfied. And finally, condition (3) means that f (x) | f (xn ) (mod pri i ) for all i, and so the Frobenius step is satisfied modulo n. If all gcmd calculations exist modulo n, then they exist modulo pri i for all i, so to finish the proof we need to show that the latter condition is sufficient to ensure gcmd(xn − x, f (x)) and 2 gcmd(xn − x, f (x)) exist. Since gcmd(xn − x, f (x)) = 1 (mod pri i ) for all i, by [Gra01, Proposition

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

5

2

3.4] we know that gcmd(xn − x, f (x)) = 1 (mod n) and thus exists. If gcmd(xn − x, f (x)) = f (x) 2 (mod pri i ), then pri i divides xn −x−f (x)gi (x) for some polynomial gi (x). However, using the Chinese remainder theorem on each coefficient in turn, we can construct a polynomial g(x) ∈ (Z/nZ)[x] such 2 that g(x) = gi (x) (mod pri i ) for all i. Then for all i, pri i divides xn − x − f (x)g(x) and hence n 2 2 divides xn − x − f (x)g(x). This shows that gcmd(xn − x, f (x)) = f (x) (mod n), and in particular that it exists. Remark 7. It is worth noting that the existence of a gcmd does not imply that the Euclidean algorithm will not detect a factorization of n while computing it. That said, for the calculations involved in checking for degree-2 Frobenius pseudoprimes this can only happen in the (∆ | n) = −1 case and only if either n is even or if one of the conditions (1-4) of Proposition 6 would already fail. When n is even, it will only discover a power of 2 (and the complementary factor). The rest of this remark justifies these claims. First, assume the Euclidean algorithm would discover factors of n. If the Factorization 1 and Factorization 2 conditions are passed then it implies there exist primes pi and pj , such that at some iteration of the Euclidean algorithm to compute gcmd(xn − x, f (x)), the degrees of the polynomials being considered differ. We note that given gcmd(xn − x, f (x)) = 1 (mod n) we must have for each p | n that xn − x = f (x)g(x) + ax + b

(mod p)

where either a = 0 and b is a unit, or a is a unit. However, if a = 0, then condition (Frobenius) implies the roots of f (x) modulo p are α and α+b. But this can only happen for p = 2. In particular, if n is odd, then we must have that a 6= 0 is a unit for all p | n and thus Given that

gcmd(xn

xn − x = f (x)g(x) + ax + b

(mod n) .

− x, f (x)) = 1 (mod n) we then have that

f (x) = (ax + b)h(x) + e (mod n)

where e is a unit. It follows that the only possible discrepancy between pi and pj is if one of the primes is 2. Finally, the Euclidean algorithm will not discover a factor of n while computing gcmd(f (x), g(x)) if the result is f (x). 3. Monier formula for degree-2 Frobenius pseudoprimes In this section we give explicit formulas, analogousQto those of Monier [Mon80] for F (n), for the quantity L2 (n) of polynomials f (x) modulo n = i pri i for which n is a degree-2 Frobenius pseudoprime. The key step will be reinterpreting the conditions of the previous section in terms of conditions on the roots α and β of f (x) modulo pri i for each i. As in the previous section, it shall be useful to distinguish the cases (∆ | n) = ±1, and as such we will give separate formulas for L± 2 (n). Notation. For each fixed value of n, denote by L+ 2 (n) the total number of quadratic polynomials f (mod n) such that (f, n) is a liar pair and (∆ | n) = +1. For each fixed value of n, denote by L− 2 (n) the total number of quadratic polynomials f (mod n) such that (f, n) is a liar pair and (∆ | n) = −1.

At the heart of the formula is the size and structure of the ring R := (Z/pr Z)[x]/hf (x)i, so we spend a little time discussing some basic facts. Recall that in the case where r = 1, if (∆ | p) = 1 then R ≃ Fp ⊗ Fp and |R× | = (p − 1)2 , while if (∆ | p) = −1 then R ≃ Fp2 and R× is cyclic of order p2 − 1. When r > 1 we have the canonical surjective homomorphism φ : (Z/pr Z)[x]/hf (x)i → (Z/pZ)[x]/hf (x)i

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

6

and a similar map on the unit groups. Furthermore, f (x) will split in Z/pr Z if and only if (∆ | p) = 1. Thus |R× | = p2r−2 (p − 1)2 if (∆ | p) = 1 and |R× | = p2r−2 (p2 − 1) if (∆ | p) = −1. In the latter case, since R× maps surjectively onto a cyclic group of order p2 − 1, with the kernel a p-group, it has a cyclic subgroup S of order p2 − 1. This fact follows from the fundamental theorem of abelian groups [Lan02, Exercise 1.43], and implies that there is a section of φ yielding a bijective homomorphism from S to (Z/pZ)[x]/hf (x)i. 3.1. The case (∆ | n) = +1. We note that in this case there must be an even number of primes pi for which ri is odd and (∆ | p) = −1. In order to count the number of f (x) modulo n, we shall count for each i the number of modulo ri pi false witnesses for which (∆ | p) = ±1. By the Chinese remainder theorem, the desired count is then the product for all combinations which ensure above parity condition. Lemma 8. The number of degree 2 polynomials over (Z/pr Z) with (∆ | n) = +1 and (∆ | p) = +1 which satisfy the conditions of being a quadratic Frobenius pseudoprime at p is exactly 1 L++ gcd(n − 1, p − 1)2 − gcd(n − 1, p − 1) . 2 (n, p) = 2 Proof. Referring to Proposition 5, gcmd(xn − x, f (x)) = f (x) (mod pr ) means that αn = α and β n = β modulo pr for roots α, β of f (x). In addition, the roots are distinct and nonzero by the integer divisibility condition. The group (Z/pr Z)× is cyclic, so it has gcd(n − 1, pr−1 (p − 1)) = gcd(n − 1, p − 1) elements whose order divides both n − 1 and p − 1. Choosing two such elements, which are not congruent modulo p, gives the result. Lemma 9. The number of degree 2 polynomials over (Z/pr Z) with (∆ | n) = +1 and (∆ | p) = −1 which satisfy the conditions of being a quadratic Frobenius pseudoprime at p is exactly 1 gcd(n − 1, p2 − 1) − gcd(n − 1, p − 1) . L+− 2 (n, p) = 2 Proof. We again refer to Proposition 5. Since (∆ | p) = −1, R := (Z/pr Z)[x]/hf (x)i maps surjectively onto Fp2 and the cofactor has size p2r−2 . Furthermore, the distinct, nonzero roots α, β of r f (x) are not lifts of elements of Fp , and αp = β (mod pr ). The factorization condition implies that αn = α (mod pr ), so that the order of α in R× divides n − 1. All elements of R× have order dividing p2r−2 (p2 − 1). Hence the number of options for α is exactly gcd(p2 − 1, n − 1) − gcd(p − 1, n − 1), and we divide by 2 since the polynomial f (x) (mod pr ) is symmetric in α and β. In order to capture the requirement that we have an even number of contributions from primes where (∆ | p) = −1 when ri is odd, we anti-symmetrize with respect to these terms to obtain the formula for L+ 2 (n). Theorem 10. The number of degree 2 polynomials over (Z/nZ) with (∆ | n) = +1 which give a quadratic Frobenius pseudoprime is exactly 1 Y ++ Y ++ 1 Y ++ +− L2 (n, pi ) − L+− . L2 (n, pi ) + L+− (n, p ) + L (n, p ) + L (n, p ) i i i 2 (n, pi ) 2 2 2 2 2 i

2|ri

2∤ri

Corollary 11. If n is squarefree, the formula in Theorem 10 becomes 1 Y1 L+ gcd(n − 1, p2 − 1) + gcd(n − 1, p − 1)2 − 2 gcd(n − 1, p − 1)) 2 (n) = 2 2 p|n

+

1Y1 gcd(n − 1, p − 1)2 − gcd(n − 1, p2 − 1)) . 2 2 p|n

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

7

3.2. The case (∆ | n) = −1. In this case there must be an odd number of primes pi for which ri is odd and (∆ | p) = −1. As above, the liar count is first computed separately for each p. Lemma 12. The number of degree 2 polynomials over (Z/pr Z) with (∆ | n) = −1 and (∆ | p) = +1 which satisfy the conditions of being a quadratic Frobenius pseudoprime at p is exactly L−+ 2 (n, p) =

1 gcd(n2 − 1, p − 1) − gcd(n − 1, p − 1) . 2

Proof. Since (∆ | p) = 1, the roots α, β of f (x) are in (Z/pr Z). Referring to Proposition 6, the roots are distinct and nonzero by the integer divisibility condition. Furthermore, gcmd(xn − x, f (x)) = 1 2 means that αn 6= α (mod pr ), but we do have αn = α (mod pr ) by the factorization 2 condition. The Frobenius condition implies αn is a root of f (x), and thus αn = β. The group (Z/pr Z)× is cyclic of order pr−1 (p − 1), and so the number of elements with order dividing both n2 − 1 and pr−1 (p − 1) is gcd(n2 − 1, p − 1). We subtract off the subset of elements with order dividing n − 1, then divide by 2 since f (x) (mod pr ) is symmetric in α and β. Lemma 13. The number of degree 2 polynomials over (Z/pr Z) with (∆ | n) = −1 and (∆ | p) = −1 which satisfy the conditions of being a quadratic Frobenius pseudoprime at p is exactly L−− 2 (n, p) =

1 gcd(p2 − 1, n2 − 1, n − p) − gcd(n − 1, p − 1) . 2

Proof. Since (∆ | p) = −1, R := (Z/pr Z)[x]/hf (x)i maps surjectively onto Fp2 and R× has order p2r−2 (p2 − 1). Furthermore, roots α, β of f (x) are not in Z/pr Z, and by the divisibility condition in Proposition 6 we know those roots are distinct units modulo p. The factorization conditions tell 2 us that αn = α (mod pr ) and the Frobenius condition implies αn = β (mod pr ). We claim a further relation on the roots, namely that αp = β (mod p) implies αp = β (mod pr ). Recall from the discussion above that R× has a cyclic subgroup S of order p2 −1. The multiplicative orders of α, β divide n2 − 1, and since those orders are not divisible by p we have α, β ∈ S. Let g be a generator and write α = ga , β = gb . Then αp = β (mod p) implies g pa−b = 1 (mod p). Since , p2 − 1 | pa − b and hence αp = β in the image of g under reduction modulo p is a generator of F× p2 S, i.e. αp = β (mod pr ). We conclude that the order of α in R× must divide n2 − 1, p2r−2 (p2 − 1), and n − p. The number of options for α is thus exactly gcd(p2 − 1, n2 − 1, n − p) − gcd(p − 1, n − 1), and we divide by 2 since the polynomial f (x) (mod pr ) is symmetric in α and β. In order to capture the requirement that we have an odd number of contributions from primes where (∆ | p) = −1 when ri is odd, we anti-symmetrize with respect to these terms to obtain the formula for L− 2 (n). Theorem 14. The number of degree 2 polynomials over (Z/nZ) with (∆ | n) = −1 which give a quadratic Frobenius pseudoprime is exactly Y −+ 1 Y −+ 1 Y −+ −− L2 (n, pi ) − L−− . L (n, p ) + L (n, p ) L2 (n, pi ) + L−− (n, p ) − i i i 2 (n, pi ) 2 2 2 2 2 i

2|ri

2∤ri

Corollary 15. If n is squarefree, the formula in Theorem 14 becomes 1 Y1 L− gcd(n2 − 1, p − 1) + gcd(n2 − 1, p2 − 1, n − p) − 2 gcd(n − 1, p − 1) 2 (n) = 2 2 p|n

−

1Y1 gcd(n2 − 1, p − 1) − gcd(n2 − 1, p2 − 1, n − p) . 2 2 p|n

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

8

− 3.3. Upper bounds. In this section we give simpler upper bounds for L+ 2 (n) and L2 (n), which will be needed in Section 6.

Lemma 16. If n is a composite integer then Y L+ max(gcd(n − 1, p2 − 1), gcd(n − 1, p − 1)2 ) and 2 (n) ≤ p|n

L− 2 (n)

≤

Y p|n

gcd(n2 − 1, p2 − 1) .

+− Proof. For each prime factor p of n, we choose the greater of L++ 2 (n, p) and L2 (n, p). That is, Y Y +− L+ max(L++ max(gcd(n − 1, p − 1)2 , gcd(n − 1, p2 − 1)) . 2 (n) ≤ 2 (n, pi ), L2 (n, pi )) ≤ i

p|n

For L− 2 (n) a similar argument gives the simpler upper bound Y Y max(gcd(n2 − 1, p2 − 1, n − p), gcd(n2 − 1, p − 1)) ≤ gcd(n2 − 1, p2 − 1) . p|n

p|n

3.4. The vanishing of L− 2 (n). A major theme of this work is that odd composites have many quadratic Frobenius liars on average, even if we restrict to the case (∆ | n) = −1. With this in − − mind, it is useful to note that L− 2 (n) can be 0. For example, L2 (9) = 0 and L2 (21) = 0. As a first general example, write n = ps with gcd(p, s) = 1. If the quantities gcd(p2 − 1, n2 − 1, n − p) − gcd(n − 1, p − 1)

and

gcd(n2 − 1, p − 1) − gcd(n − 1, p − 1)

are both zero, then it is immediate from Theorem 14 that L− 2 (n) = 0. These conditions are met if whenever ℓr | gcd(p2 − 1, n2 − 1, n − p) or ℓr | gcd(n2 − 1, p − 1) we also have ℓr | gcd(n − 1, p − 1). For odd primes ℓ | p2 − 1 this is accomplished by the requirement that s 6= −p−1

(mod ℓ) ,

as this implies that if ℓ | p2 − 1 then ℓ ∤ sp + 1. For the prime 2, if we write p = 1 + 2r (mod 2r+1 ) then the requirement s = 1 + 2r (mod 2r+1 ) implies the exact power of 2 dividing each of gcd(p2 − 1, n2 − 1, n − p), gcd(n2 − 1, p − 1), and gcd(n − 1, p − 1) is 2r . A more general example comes from Carmichael numbers, which are squarefree n with gcd(n − 1, p − 1) = p − 1 for all primes p | n. Remark 17. If n is a classical Carmichael number, then L−+ 2 (n, p) = 0 for all p and Y1 L− gcd(n2 − 1, p2 − 1, n − p) − gcd(n − 1, p − 1) 2 (n) = 2 p|n

if n has an odd number of prime factors, and 0 otherwise (see Corollary 15). In particular, the only f for which (f, n) would be liar pair with (∆ | n) = −1 have f inert at all primes dividing n. Furthermore, if n = 1 (mod 4)Qthen for each p | n with p = 3 (mod 4) we naively estimate the ′ ℓ−2 probability that L−− 2 (n, p) = 0 as ℓ|p+1 ℓ−1 , where the product is over odd primes ℓ.

As a final example, let n be a rigid Carmichael number of order 2 in the sense of [How00], so that n is squarefree and p2 − 1 | n − 1 for every prime factor p of n. Then gcd(n2 − 1, p2 − 1, n − p) = gcd(n − 1, p − 1) and gcd(n2 − 1, p − 1) = gcd(n − 1, p − 1), so that L− 2 (n) = 0.

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

9

4. Number theoretic background Notation. Let L be an upper bound for Linnik’s constant. That is, the constant L satisfies: if (a, m) = 1 then there exists p = a

(mod m) with p < mL .

It is known that L ≤ 5. (See [Xyl11]) For each value x denote by M (x) the least common multiple of all integers up to

log(x) log log(x) .

(+)

For each value x and for each α > 0 denote by Pα (x) the set {prime p < (log(x))α such that (p − 1) | M (x)}

(−)

and by Pα (x) the set

prime p < (log(x))α such that (p2 − 1) | M (x) .

Now, given functions M1 (x) and M2 (x) of x which satisfy M (x) = M1 (x)M2 (x)

and

gcd(M1 (x), M2 (x)) = 2

we define for each value x and for each α > 0 the set Pα (M1 (x), M2 (x), x) = {prime p < (log(x))α such that (p − 1) | M1 (x) and (p + 1) | M2 (x)} . Proposition 18. We have M (x) = xo(1) . Proof. We can estimate M (x) by: Y

p

j

log log(x)−log log log(x) log(p)

k

<

Y

log(x) p< log log(x)

log(x) p< log log(x)

log(x) = log log(x)

log(x) log log(x)

π

log(x) log log(x)

= xo(1) .

The next two propositions follow from results on the smoothness of shifted primes. The conclusion (+) (−) is that the sets Pα (x) and Pα (x) are relatively large. As a comparison, by the prime number x)α theorem the asymptotic count of all primes p < (log x)α is α(log log log x . (+) Proposition 19. There exists α > 1 such that Pα (x) > log(x)α−o(1) . In particular we may take α = 23/8. The result follows from work of Erd˝os; the best bound is from [Bal84]. (−) Proposition 20. There exists α > 1 such that Pα (x) > log(x)α−o(1) . In particular we may take α = 4/3. The result as well as the best bound is from [DMT01]. The next proposition is a novel contribution to the theory of constructing pseudoprimes. (−) Proposition 21. Given α such that Pα (x) > log(x)α−o(1) , there exist M1 (x), M2 (x) such that |Pα (M1 (x), M2 (x), x)| > log(x)α−o(1) .

Proof. Let M be the fixed choice of M (x) that follows from a fixed choice of x. Each prime (−) p ∈ Pα (x) is also in Pα ((p − 1)d1 , (p + 1)d2 , x) for all pairs (d1 , d2 ) satisfying d1 d2 =

M p2 − 1

and

gcd(d1 , d2 ) = 1 .

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

10

The number of pairs (M1 , M2 ) satisfying the conditions laid out in the notation comment at the beginning of the section is 2π(log(x)/ log log(x)) since each prime up to logloglogx x is assigned to either M1 or M2 . To count the number of choices for d1 and d2 we subtract from the exponent the count of prime factors of p2 − 1. This work yields X

M1 ,M2

|Pα (M1 , M2 , x)| =

X

(−)

p∈Pα

ω

2

M p2 −1

π

>2

log x log log x

−ωmax (p2 −1)

(log x)α−o(1)

(x)

where ωmax (p2 − 1) denotes the maximum number of distinct prime factors of p2 − 1 for all p under consideration. Because ωmax (p2 − 1) is log((p2 − 1)o(1) ) we obtain the estimate 2ωmax (p

2 −1)

< (p2 − 1)o(1) < (log x)o(1) .

Now, if |Pα (M1 , M2 , x)| < (log x)α−o(1) for all pairs (M1 , M2 ) we would conclude that X

π

M1 ,M2

|Pα (M1 , M2 , x)| < 2

log x log log x

(log x)α−o(1) ,

but since this contradicts the earlier lower bound we instead conclude that |Pα (M1 , M2 , x)| > (log x)α−o(1) for at least one pair (M1 , M2 ). Remark 22. From the proof we expect the result will in fact hold for most choices of M1 and M2 . The proof we have given does not actually imply any relationship between Mi (x) for different values of x. In particular, though one perhaps expects that that there exists a complete partitioning of all primes into two sets and that the Mi are simply constructed by considering only those primes in the given range, we do not show this. It is generally expected (see for example [EP86]) that the values α under consideration can be taken arbitrarily large. In particular we expect the following to hold. Conjecture 23. In each of the above three propositions, the result holds for all α > 0. The following lemma will be useful in the next section. Lemma 24. Fix n and p | n. If n = −1 (mod q) and p = 1 (mod q) for q ≥ 3 then gcd(n2 − 1, p − 1) − gcd(n − 1, p − 1) > 0 . If n = −1 (mod q) and p = −1 (mod q) for q ≥ 3 then gcd(n2 − 1, p2 − 1, n − p) − gcd(n − 1, p − 1) > 0 . If n = p = 1 (mod 2) then gcd(n − 1, p − 1)2 − gcd(n − 1, p − 1) > 0 . Proof. For n = −1 (mod q) and p = 1 (mod q) we have q | gcd(n+1, p−1) while q ∤ gcd(n−1, p−1). If n = −1 (mod q) and p = −1 (mod q) then q | gcd(n2 − 1, p2 − 1, n − p) and q ∤ gcd(n − 1, p − 1). Finally, for n = p = 1 (mod 2) it follows that gcd(n − 1, p − 1) > 1, and so gcd(n − 1, p − 1)(gcd(n − 1, p − 1) − 1) is nonzero.

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

11

5. Lower bounds on the average number of degree-2 Frobenius pseudoprimes In this section we will prove the lower bound portion of the two theorems in the introduction. Specifically we shall prove the following results. Theorem 25. For any value of α > 1 satisfying Proposition 19 we have the asymptotic inequality X 3−α−1 −o(1) L+ . 2 (n) ≥ x n

Theorem 26. For any value of α > 1 satisfying Proposition 20 we have the asymptotic inequality X 3−α−1 −o(1) L− . 2 (n) ≥ x n

The proofs of the above two theorems are at the end of this section. We shall first introduce some notation and prove several necessary propositions. Notation. For fixed 0 < ǫ < α − 1 and for all x > 0 let k j (+) log(M ) , • kα (x) = log(x)−L j α log log(x) k (−) log(M ) • kα (x) = log(x)−2L , α log log(x) (+)

(+)

• Sα,ǫ (x) be the set of integers s which are the product of kα (x) distinct elements from (+)

Pα(+) (x) \ Pα−ǫ (x) ,

(−)

• Sα,ǫ (M1 (x), M2 (x), x) be the set of integers s which are the product of the largest odd number (−) not larger than kα (x) many distinct elements from Pα (M1 (x), M2 (x), x) \ Pα−ǫ (M1 (x), M2 (x), x) . The following two claims are immediate consequences of the construction. (+)

Claim. The elements s of Sα,ǫ (x) all satisfy x1−o(1) (+) x log(x)−kα (x)ǫ

Claim. The elements s of Sα,ǫ (x) all satisfy x1−o(1) (−) x < s < 2L . log(x)−kα (x)ǫ L M M

(±)

The next two propositions follow from the lower bound on the size of Pα (±) kα .

and the definition of

Proposition 27. If α satisfies the conditions of Proposition 19 then −1 (+) Sα,ǫ (x) > x1−α +o(1) .

(+) Proof. A standard bound on a binomial coefficient is given by nk ≥ (n/k)k . We are choosing kα α−o(1) − (log x)α−ǫ = (log x)α−o(1) . The resulting lower many primes from a set of size at least (log x) (+) bound on Sα,ǫ (x) is (log x)α−o(1) (log x)1+o(1)

! log(x)−L log(M ) −1 α log log(x)

−1 +o(1))

≥ ((log x)α−1+o(1) )(α

log x log log x

−1 +o(1)

= x1−α

.

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

12

Proposition 28. If α, M1 (x), and M2 (x) satisfy the conditions of Proposition 21 then −1 (−) Sα,ǫ (M1 (x), M2 (x), x) > x1−α +o(1) . Proof. The proof is identical to that of Proposition 27.

The next two propositions construct a composite n with many degree-2 Frobenius liars. The strategy in the plus one case is to start with a composite s that is the product of many primes p such that p − 1 is smooth, then find a prime q such that n = sq is congruent to 1 modulo M . While the liar count primarily comes from the primes p dividing s, we need to ensure at least one modulo q liar, else the entire modulo n liar count becomes 0. Lemma 29. As before, let L be an upper bound for Linnik’s constant. Given any element s of (+) Sα,ǫ (x) there exists a prime q < M L such that • sq = 1 (mod M ), • gcd(q, s) = 1, and • 21 gcd(q − 1, sq − 1)2 − gcd(q − 1, sq − 1) > 0. 2

Moreover, the number of liars of n = sq with (∆ | n) = +1 is at least x2−ǫ α −o(1) . (+)

Proof. By construction, every s ∈ Sα,ǫ (x) satisfies gcd(s, M ) = 1. Then by the definition of L, we can choose M < q < M L to be the smallest prime such that sq = 1 (mod M ). Since q > M and the factors of s are all smaller than M , we have gcd(q, s) = 1. With q, n both odd, the third condition follows from Lemma 24. For a lower bound on L+ 2 (n) for n = sq we count only the liars from primes p | s with (∆ | p) = +1. This gives Y Y1 (gcd(n − 1, p − 1)2 − gcd(n − 1, p − 1)) L++ (n, p) = 2 2 p|s

p|s

by Lemma 8. By construction, for p | s we have p − 1 | M and M | n − 1, so the product becomes Y (+) (+) 2−kα (x) (p − 1)(p − 2) ≥ 2−kα (x) · s2−o(1) p|s

(+) ≥ x−o(1) log(x)−kα (x)ǫ(2−o(1)) 2

≥ x−o(1) x−ǫ· α (1+o(1))

x2−o(1) M L(2−o(1))

2 x2−o(1) = x2−ǫ α −o(1) o(1) x

where the upper bound on M comes from Proposition 18.

In the minus one case we have two different divisibility conditions to satisfy, and as a result require two primes q1 and q2 to complete the composite number n. (−)

Lemma 30. Let L be an upper bound for Linnik’s constant. Given any element s of Sα,ǫ (x) there exists a number q < M 2L such that • sq = 1 (mod M1 ), • sq = −1 (mod M2 ), • gcd(q, Q 1 s) = 1, and • p|q 2 gcd((sq)2 − 1, p − 1) − gcd(sq − 1, p − 1) > 0.

Moreover, the number of liars of n = sq with (∆ | n) = −1 is at least Y (−) 2 p2 − 1 = x2−ǫ α −o(1) . 2−kα (x) p|s

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

13

Proof. We construct q as the product of two primes q1 and q2 . Let ℓ1 , ℓ2 be two distinct odd primes which divide M2 and write M2 = M2′ ℓr11 ℓr22 . Choose q1 to be the smallest prime greater than M satisfying the following four conditions: sq1 = −1 (mod M2′ ) sq1 = −1 (mod ℓr22 )

sq1 = 1 (mod M1 ) q1 = 1 (mod ℓr11 )

and choose q2 to be the smallest prime greater than M satisfying the following four conditions: q2 = 1 (mod M2′ ) q2 = 1 (mod ℓr22 ) .

q2 = 1 (mod M1 ) sq2 = −1 (mod ℓr11 )

Note that q1 , q2 > M implies they are greater than any factor of s, and thus relatively prime to s. Then q1 , q2 exist due to the definition of Linnik’s constant, with q1 , q2 < (M1 M2′ ℓr11 ℓr22 )L so that q < M 2L . Note sq1 q2 = 1 (mod M1 ), which satisfies the first bulleted condition. In addition, sq1 q2 = −1 (mod M2′ ), sq1 q2 = −1 (mod ℓr11 ), and sq1 q2 = −1 (mod ℓr22 ) so that sq = −1 (mod M2 ). For the fourth bullet point, sq1 q2 = −1 (mod ℓr11 ) and q1 = 1 (mod ℓr11 ) gives the result by Lemma 24. To bound L− 2 (n) we select only n where (∆ | p) = +1 for all p | q and (∆ | p) = −1 for all p | s. By Lemma 13 we have Y1 Y gcd(p2 − 1, n2 − 1, n − p) − gcd(n − 1, p − 1) L−− 2 (n, p) = 2 p|s

p|s

(−)

= 2−kα

(x)

Y (p2 − 1) − (p − 1) p|s

2

since by construction p − 1 | n − 1 and p + 1 | n + 1. This product is x2−ǫ α −o(1) by the same argument as that in Lemma 29. Proof of Theorems 25 and 26. In each case the theorem is an immediate consequence of the lower bounds on the number of liars for each value of n = sq constructed in Lemma 29 or 30, together with the size of the set S under consideration. (±) More specifically, for each element s of Sα,ǫ (x), by Lemma 29 or 30 we can associate a distinct 2 2−ǫ α −o(1) . For each of the plus, minus cases we have that number n with L± 2 (n) > x −1 (±) Sα,ǫ (x) > x1−α −o(1) for α satisfying as appropriate Proposition 19 or 20. We conclude that for all ǫ > 0 and appropriately chosen α we have X 2 3−α−1 −ǫ α −o(1) L± . 2 (n) > x n

Allowing ǫ to go to 0, we obtain the result.

6. Upper bounds on the average number of degree-2 Frobenius pseudoprimes Our proof will follow [EP86, Theorem 2.2] quite closely. First we need a key lemma, the proof of which follows a paper of Pomerance [Pom81, Theorem 1]. Notation. Given an integer m, define λ(m) = lcm(p − 1) p|m

and

λ2 (m) = lcm(p2 − 1) . p|m

Note that λ(m) is not Carmichael’s function, though it is equivalent when m is squarefree. Moreover, given x > 0 we shall define log(x) log 3 (x) L(x) = exp log2 (x)

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

14

where log2 (x) = log log(x) and log3 (x) = log log log(x). Here log is the natural logarithm. Lemma 31. For all sufficiently large x we have #{m ≤ x : λ2 (m) = n} ≤ x · L(x)−1+o(1) . Proof. For c > 0 we have X 1 ≤ xc m≤x λ2 (m)=n

X

λ2 (m)=n

m−c ≤ xc

X

p|m⇒p2 −1|n

m−c ≤ xc

By the theory of Euler products, we can rewrite the sum as A. With c = 1 −

log3 (x) log2 (x) ,

Q

X

m−c .

p|m⇒p−1|n

p−1|n (1

− p−c )−1 . Call this product

the result follows if we can show that log A = o(log(x)/ log 2 (x)). log (x)

Take x large enough so that log3 (x) ≤ 21 ; from this it follows that for all primes p, 1−p1 −c ≤ 4. 2 Following Pomerance in [Pom81, Theorem 1], via the Taylor series for − log(1 − x) we can show that X p−c X Y −c log A = d ≤ 4 (1 − p−c )−1 ≤ 4 1 − p−c p−1|n

d|n

and similarly

log log A ≤ log(4) +

X p|n

p|n

X p−c ≤ log(4) + 4 p−c . 1 − p−c p|n

Since the sum is maximized with many small primes, an upper bound is X (log x)1−c −c log(4) + 4p = O (1 − c) log log x p≤4 log x

where the sum is evaluated using partial summation. With c = 1 − log3 (x)/ log 2 (x) we achieve log2 (x) log log A = O log3 (x)

so that log A = o(log(x)/ log 2 (x)) as requested.

An interesting question is whether the upper bound in that lemma can be lowered. If so, a more clever upper bound would be required for the sum over primes p dividing m such that p2 − 1 | n. In [EP86] the key idea is to parameterize composite n according to the size of the subgroup of Fermat liars, and then to prove a useful divisibility relation involving n. Here we reverse this strategy: we parameterize according to a divisibility condition and prove an upper bound on the size of the set of Frobenius liars. Lemma 32. Assume n is composite and let k be the smallest integer such that λ2 (n) | k(n2 − 1). Then 1Y 2 (p − 1) . L− (n) ≤ 2 k p|n

Proof. We have k = λ2 (n)/ gcd(λ2 (n), n2 − 1). Our goal will be to show that Y Y λ2 (n) 2 2 (1) p2 − 1 . gcd(p − 1, n − 1) 2 gcd(λ2 (n), n − 1) p|n p|n

If this is true, then combined with Lemma 16 we have Y 1Y 2 p −1 . L− gcd(n2 − 1, p2 − 1) ≤ 2 (n) ≤ k p|n

p|n

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

15

Fix arbitrary prime q and let q ei be the greatest power of q that divides p2i − 1. Suppose we have ordered the r primes dividing n according to the quantity ei . Let q d be the power of q that divides n2 − 1. Consider first the case where d ≥ er , the largest of the ei . Then q er divides λ2 (n) since it is 2 defined as an lcm of Q the p2 − 1, and q er divides gcd(λ2 (n), n Q − 1)2 since d ≥ er . We are left with 2 2 the observation that p|n gcd(p − 1, n − 1) is a divisor of p|n p − 1, and thus in particular the q power divides. Next consider the case where d ≥ ei for i ≤ ℓ and d < ei for i > ℓ. Then q er divides λ2 (n) since it is defined as an lcm, and q d divides gcd(λ2 (n), n2 − 1) since d < er . The total power of q dividing P the LHS is then er − d + ( ℓi=1 ei ) + (r − ℓ)d. We have ! ! ℓ ℓ X X ei + d(r − ℓ − 1) + (d + er − d) ei + er − d + d(r − ℓ) = i=1 ℓ X

i=1

≤ =

ei

i=1 r X

!

+

r−1 X

ei

i=ℓ+1

!

+ er

ei ,

i=1

which is the power of q dividing proof.

Q

p2 − 1. Since q was arbitrary, (1) holds, which finishes the

The result for L+ 2 (n) is similar. We do need a new piece of notation, namely given a prime p we shall define ( (p − 1)2 if gcd(n − 1, p − 1)2 > gcd(n − 1, p2 − 1) dn (p) = p2 − 1 if gcd(n − 1, p − 1)2 ≤ gcd(n − 1, p2 − 1) . Lemma 33. Suppose n is composite and let k be the smallest integer such that λ(n) | k(n − 1). Then 1Y dn (p) . L+ 2 (n) ≤ k p|n

Proof. From Lemma 16 we know that Y L+ max(gcd(n − 1, p2 − 1), gcd(n − 1, p − 1)2 ) 2 (n) ≤ p|n

and from the definition of k we know that k is exactly λ(n)/ gcd(λ(n), n − 1). It thus suffices to show that Y Y λ(n) 2 2 (2) dn (p) . max(gcd(n − 1, p − 1), gcd(n − 1, p − 1) ) gcd(λ(n), n − 1) p|n p|n For an arbitrary prime q, let q ei be the power of q dividing dn (p) and let q d be the power of q dividing n − 1. Order the that d ≥ ei for i ≤ ℓ and d < ei for i > ℓ. Then the Q ei , and suppose Pr exponent of q dividing p|n dn (p) is i=1 ei . Following the same argument as in Lemma 32, the exponent of q dividing the left hand side of (2) is ! r ℓ X X ei . ei + (r − ℓ)d ≤ (er − d) + i=1

Since q was arbitrary, the division in (2) holds.

i=1

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

16

Theorem 34. For all sufficiently large x we have ′ X

n≤x

where

P′

L2 (n) ≤ x3 L(x)−1+o(1)

signifies the sum is only over composite integers.

Proof. Let Ck (x) denote the set of composite n ≤ x where k is the smallest integer such that λ(n) | k(n − 1), and let Dk (x) denote the set of composite n ≤ x where k is the smallest integer 2 such that λ2 (n) | k(n2 − 1). By Lemma 32, if n ∈ Dk (x) then L− 2 (n) ≤ n /k. Similarly, by Lemma 2 33, if n ∈ Ck (x) then L+ 2 (n) ≤ n /k. Then ′ X

L2 (n) =

′ X

− L+ 2 (n) + L2 (n)

n≤x

n≤x

=

X X

≤

X X

L+ 2 (n) + n2 k

+

X n2 X ≤ + L(x) n≤x

=

L− 2 (n)

k n∈Dk (x)

k n∈Ck (x)

k n∈Ck (x)

X X

X X

k n∈Dk (x)

X

k≤L(x) n∈Ck (x)

n2 k

X n2 X n2 + + k L(x) n≤x

k≤L(x) n∈Dk (x)

X |Ck (x)| X |Dk (x)| 2x3 + x2 + x2 L(x) k k k≤L(x)

X

n2 k

k≤L(x)

and thus the proof is complete if we can prove that |Ck (x)| ≤ xL(x)−1+o(1) and |Dk (x)| ≤ xL(x)−1+o(1) hold uniformly for k ≤ L(x). We focus first on the Dk (x) result. For every n ∈ Dk (x), either (1) n ≤ x/L(x), p (2) n is divisible by some prime p > pkL(x), and/or (3) n ≥ x/L(x) and p | n implies p ≤ kL(x).

The number of integers in case (1) is at most xL(x)−1 by assumption. Turning to case (2), if n ∈ Dk (x) and p | n then p2 − 1 is a divisor of λ2 (n) and hence of k(n2 − 1). This means that 2 p2 − 1 n −1 . 2 gcd(k, p − 1)

A straightforward application of the Chinese remainder theorem shows that the count of residues x (mod a) with x2 = 1 (mod a) is at most 2ω(a)+1 . Thus the count of n ∈ Dk (x) with p | n is at most ' & 2 2 2xk2ω(p −1) xkL(x)o(1) 2x2ω(p −1) ≤ = . p(p2 − 1)/ gcd(p2 − 1, k) p(p2 − 1) p(p2 − 1) 2

The equality 2ω(p −1)+1 = L(x)o(1) follows from the fact that the maximum number of distinct prime factors dividing any integer m ≤ x2 is 2 log(x2 )/ log log(x2 ). We conclude that the maximum number of n in case (2) is

p>

X

√

kL(x)

2xkL(x)o(1) ≤ xkL(x)o(1) p3

p>

X

√

kL(x)

1 = xL(x)−1+o(1) . p3

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

17

For n in case (3), since all primes dividing n are small we know that n has a divisor d satisfying x x p

To construct such a divisor, remove primes from p n until the remaining integer is smaller than x/L(x); since each prime dividing n is at most kL(x) the lower bound follows. Let A be the set of d ∈ Z that fall between the bounds given. We have λ2 (d) | λ2 (n) | k(n2 − 1), and so by a similar argument we know that the number of n ∈ Dk (x) with d | n is at most xL(x)o(1) . dλ2 (d)/ gcd(k, λ2 (d))

Unlike the case where d is prime, here we might have gcd(d, λ2 (d)) 6= 1. But then the set of n ∈ Dk (x) with d | n is empty, so the bound given remains true. Now, the number of n ∈ Dk (x) in case (3) is at most X gcd(k, λ2 (d)) X xL(x)o(1) gcd(k, λ2 (d)) = xL(x)o(1) dλ2 (d) dλ2 (d) d∈A d∈A X 1 X = xL(x)o(1) m d∈A m≤x

≤ xL(x)o(1)

1 d

λ2 (d)/ gcd(k,λ2 (d))=m

X 1 X m

m≤x

u|k

X

d∈A λ2 (d)=mu

1 . d

Note that if λ2 (d)/ gcd(k, λ2 (d)) = m, then λ2 (d) = mu for some u | k, and thus summing over all u | k gives an upper bound. To evaluate the inner sum we use partial summation and Lemma 31 to get Z x/L(x) X 1 X 1 X 1 1+ ≤ 1 dt √ 2 d x/L(x) d∈A x/L(x) kL(x) t d∈A d

λ2 (d)=mu

≤ ≤

L(x) x/L(x) + x L(x/L(x))1+o(1)

λ2 (d)=mu

Z

x/L(x)

√

x/L(x)

kL(x)

t 1 dt 2 1+o(1) t L(t)

log(x) 1 p + = L(x)−1+o(1) 1+o(1) L(x/L(x)) L(x/L(x) kL(x))

for large enough x and uniformly for k ≤ L(x). Note that the count of divisors of an integer k is bounded above by 2(1+o(1)) log k/ log log k (see for instance [HW08, Theorem 317]). Thus the count in case (3) is X 1 X x x x log x (1+o(1)) logloglogk k = 2 1 ≤ 1+o(1) 1+o(1) m L(x) L(x) L(x)1+o(1) m≤x u|k

uniformly for k ≤ L(x) and large enough x. Proving |Ck (x)| ≤ xL(x)−1+o(1) uniformly for k ≤ L(x) will be similar. Here the three cases are: (1) n ≤ x/L(x), (2) n is divisible by some prime p > kL(x), and (3) n ≥ L(x) and p | n implies p ≤ kL(x). If n ∈ Ck (x) then λ(n) | k(n − 1). Thus the number of n ∈ Ck (x) with p | n is at most xk x ≤ 2 p(p − 1)/ gcd(p − 1, k) p

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

18

and so the count of n in case (2) is xL(x)−1+o(1) . For n in case (3) we know n has a divisor d satisfying x x

and so the bound of xL(x)−1+o(1) follows exactly from case (3) of [EP86, Theorem 2.2].

7. Conclusions and further work A very naive interpretation of Theorems 1 and 2 is that for any given f , you should expect that there are n for which f is a false witness. Moreover, one expects to find this in both the +1 and −1 cases. Likewise, one expects that given n, there will exist f which is a false witness in both the +1 and −1 cases. To emphasize the extent to which one should be careful with the careless use of the word ‘expect’ we remind the reader that in Section 3.4 we describe infinite families of n for which − L− 2 (n) = 0. It would perhaps be interesting to know how often L2 (n) vanishes for n < x. It is useful to note that this vanishing described in Section 3.4 gives some heuristic evidence to suggest that the Baillie-PSW test is significantly more accurate than other primality tests. Further work to make these heuristics more precise may be worth pursuing. In contrast to the above the proof of Theorem 2 suggests that one should expect there to exist many Frobenius-Carmichael numbers (see [Gra01] for a definition) relative to quadratic fields K for which (n | δK ) = −1. It is likely this heuristic can be extended to show that for each fixed quadratic field K there exists (infinitely many) Frobenius-Carmichael numbers n relative to K with (n | δK ) = −1. As such a number would also be a classical Carmichael number, such numbers would tend to lead to a failure of the Baillie-PSW test. If this could be done for all K it would show that all f admit n for which f is a false witness and the Jacobi symbol is −1. It remains an open problem to prove such numbers exist. It remains unclear from our results if the expected value of L− 2 (n) is actually less (in an asymptotic sense) than the expected value of L+ (n). Various heuristics suggest that it ought to be. A result of 2 this sort would put further weight behind the Baillie-PSW test. 8. Acknowledgments The Authors would like to thank Carl Pomerance for several comments which improved the results presented. References [Bal84] [BW80] [DMT01] [EP86] [Gra01] [How00] [HW08]

[Lan02] [Mon80] [Pom81] [PSW80]

Antal Balog, p + a without large prime factors, Seminar on number theory, 1983–1984 (Talence, 1983/1984), Univ. Bordeaux I, Talence, 1984, pp. Exp. No. 31, 5. MR 784077 Robert Baillie and Samuel S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391– 1417. MR 583518 C´ecile Dartyge, Greg Martin, and G´erald Tenenbaum, Polynomial values free of large prime factors, Period. Math. Hungar. 43 (2001), no. 1-2, 111–119. MR 1830570 Paul Erd˝ os and Carl Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), no. 173, 259–279. MR 815848 Jon Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), no. 234, 873–891. Everett W. Howe, Higher-order Carmichael numbers, Math. Comp. 69 (2000), no. 232, 1711–1719. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, sixth ed., Oxford University Press, Oxford, 2008, Revised by D. R. Heath-Brown and J. H. Silverman, With a foreword by Andrew Wiles. MR 2445243 Serge Lang, Algebra, third ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002. Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244 Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717 Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff, Jr., The pseudoprimes to 25 · 109 , Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872

AVERAGE LIAR COUNT FOR DEGREE-2 FROBENIUS PSEUDOPRIMES

[Xyl11]

19

¨ Triantafyllos Xylouris, Uber die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, Bonner Mathematische Schriften [Bonn Mathematical Publications], 404, Universit¨ at Bonn, Mathematisches Institut, Bonn, 2011, Dissertation for the degree of Doctor of Mathematics and Natural Sciences at the University of Bonn, Bonn, 2011. MR 3086819

Mathematics & Statistics 612 Campus Place N.W. University of Calgary 2500 University Drive NW Calgary, AB, Canada T2N 1N4 E-mail address: [email protected] Illinois Wesleyan University, 1312 Park St, Bloomington, IL, 61701 USA E-mail address: [email protected]