Arithmetic Progressions of Length Three in Multiplicative Subgroups of $\mathbb{F}_p$
Jeremy F Alm



Anomalous bulk-edge correspondence in continuous media
    A. Venaille
    December 30, 2023
======================================================






In this paper, we give an algorithm for detecting non-trivial 3-APs in multiplicative subgroups of 𝔽_p^× that is substantially more efficient than the naive approach.  It follows that certain Var der Waerden-like numbers  can be computed in polynomial time.  




§ INTRODUCTION


Additive structures inside multiplicative subgroups of ^× have recently received attention.  Alon and Bourgain <cit.> study solutions to x+y=z in H<^×, and Chang <cit.> studies arithmetic progressions  in H<^×. In this paper, we define a Van der Waerden-like number for H<^× of index n, and give a polynomial-time algorithm for determining such numbers. 



Let VW_3^×(n) denote the least prime q≡ 1 n such that for all primes p≡ 1 n with p≥ q, the multiplicative subgroup of ^× of index n contains a mod-p arithmetic progression of length three.


Our main results are the following two theorems:

VW_3^×(n) ≤ (1+ε )n^4 for all sufficiently large n (depending on ε). In particular, VW_3^×(n) ≤ 1.001n^4 for all n≥ 45. 



VW_3^×(n) can be determined by an algorithm that runs in (n^8/log n) time.


Chang <cit.> proves that if H<^× and |H|> cp^3/4, then H contains non-trivial 3-progressions. This implies our Theorem <ref> with (1+ε)n^4 replaced by cn^4.  We prove our Theorem <ref> because we need to make the constant explicit.





§ PROOF OF THEOREM <REF>



We use one of the basic ideas of the proof of Roth's Theorem on 3-progressions <cit.>. Let A⊆ with |A|=δ p. Note that a 3-progression   is a solution inside A to the equation x+y=2z.  Let 𝒩 be the number of (possibly trivial) solutions to x+y=2z inside A.  We have that 
 
    1/p∑^p-1_k=0 e^-2π ik/px= 
         
         1,     if  x≡ 0  p ;
    
         0,     if  x≢0  p.

    
  
 
 Because of (<ref>), we have
 
 
    𝒩=∑_x∈ A∑_y∈ A∑_z∈ A1/p∑_k=0^p-1 e^-2π ik/p(x+y-2z)

 
 Rearranging (<ref>), we get
 
 
 
    =  1/p∑_k=0^p-1∑_x∈ A∑_y∈ A∑_z∈ A e^-2π ik/px· e^-2π ik/py· e^2π ik/pz
       = 1/p∑_k=0^p-1[  ∑_x∈ Ae^-2π ik/px · ∑_y∈ Ae^-2π ik/py · ∑_z∈ Ae^2π ik/p2z]
       = 1/p∑_k=0^p-1[∑_x∈_A(x) e^-2π ik/px · ∑_y∈_A(y) e^-2π ik/py · ∑_z∈_A(-2z) e^2π ik/pz]
       = 1/p∑_k=0^p-1_A(k)^2·_A(-2k),

 where _A denotes the characteristic function of A, and f̂ denotes the Fourier transform of f, 
 
    f̂(x) = ∑^p-1_k=0f(k)  e^-2π ik/px .

 Now we can pull out the k=0 term from (<ref>):
 
 
    (<ref>)   = 1/p(0)^3+1/p∑_k=1^p-1_A(k)^2·_A(-2k) 
       = |A|^3/p + 1/p∑_k=1^p-1_A(k)^2·_A(-2k)
       =δ^3p^2 + 1/p∑_k=1^p-1_A(k)^2·_A(-2k).

 
 Let's call δ^3p^2 the main term, and 1/p∑_k=1^p-1_A(k)^2·_A(-k) the error term.  We now bound this error term.
 
 Suppose 0<α <1 and |_A(k)|≤α p for all 0 ≠ k∈. In this case, we say that A is α-uniform. Then
 
    |1/p∑_k=1^p-1_A(k)^2·_A(-2k)|    ≤1/pmax |_A(k)|·|∑_k=1^p-1_A(k)^2|
       ≤α|∑_k=1^p-1_A(k)^2|
       ≤α p|∑_k=1^p-1_A(k)^2|
       ≤αδ p^2.

 
 Therefore 𝒩≥δ^3 p^2-αδ p^2. Subtracting off the trivial solutions gives 𝒩-δ p≥δ^3 p^2-δ p - αδ p^2. Hence there is at least one non-trivial solution if 
 
 
    δ^3 p^2 > δ p + αδ p^2.

 
 
 Let A = H be a multiplicative subgroup of  of index n. As is well-known (see for example <cit.>), if H is a multiplicative subgroup of ^×, then H is α-uniform for α≤ p^-1/2. Thus it suffices to have
 
    δ^3 p^2≥δ p + p^-1/2δ p^2    ⟺δ^3 p^2≥δ p + δ p^3/2
       ⟺δ^2 p≥ 1 +  p^1/2
       ⟺ (p-1)^2≥ n^2 p (1 +  p^1/2)

 where the last line follows from δ = (p-1)/(np). It is straightforward to check that (<ref>) is satisfied by p=(1+ε)n^4 for sufficiently large n.
 
 


The data gathered for VW^×_3(n), n≤ 100, suggest that the exponent of 4 on n is too large; see Figure <ref>. These data are available at , sequence number A298566.





§ A MORE GENERAL FRAMEWORK

Before we establish our algorithm, it will helpful to generalize to arbitrary linear equations in three variables over .  Suppose we're looking for solutions to ax + by = cz
    in H<^×, for fixed a,b,c∈^×. There is a solution just in case (aH + bH) ∩ cH is nonempty.  
    
    The following result affords an algorithmic speedup in counting solutions to ax + by = cz inside H:
    
    
    For a, b, c∈^× and  H < ^×,
    
    (aH+bH)∩ cH ≠∅ if and only if  (c - aH)∩ bH ≠∅.

    
    
    Notice that while the implied computation on the left side of the biconditional is (p^2), the one on the right is (p), since we compute |H| subtractions and |H| comparisons. (We consider the index n fixed.) 
    
     
    Let H={ g^kn : 0 ≤ k < (p-1)/n }, where n is the index of H and g is a primitive root modulo p. Fix a,b,c ∈. 
    
    For the forward direction, suppose (aH+bH)∩ cH≠∅, so there are x,y,z ∈ H such that ax + by = cz. Then by = cz-ax. Multiplying by z^-1∈ H yields b(yz^-1) = c - a(xz^-1). Therefore (c - aH)∩ bH ≠∅.  The other direction is similar.
    
    
    Lemma <ref> allows us to detect solutions to linear equations in linear time. The caveat for the case a=b=1, c=2 is that H+H always contains 2H, since h+h=2h for all h∈ H; these solutions correspond to the trivial 3-APs h,h,h. (Similarly, (2 - H)∩ H is always nonempty, since 1∈ H and 2-1=1.)  To account for this, we simply consider H' = H∖{1}, and calculate (2 - H')∩ H' instead. 
    


§ PROOF OF THEOREM <REF>

  
  
  Here is the algorithm.
  


We now argue that Algorithm <ref> runs in (n^8/log n) time. Since calculating (2 - H')∩ H' is (p) for each prime p, our runtime is bounded by 


    ∑_p ≤ (1+ε)n^4 
     p ≡ 1 n(p) = ( ∑_p ≤ (1+ε)n^4 
     p ≡ 1 n p  ).


A standard estimate on the prime sum 

    ∑_p ≤ x 
     p ≡ 1 n p

 is asymptotically x^2/φ(n)log x, giving 
 
 
    ( ∑_p ≤ (1+ε)n^4 
     p ≡ 1 n p  ) 
                                                   = (n^8/φ(n)log(n^4)) 
       = (n^8/log(n))

 as desired.
    
  
  Our timing data suggest that the correct runtime might be more like (n^6); see Figure <ref>.
  





§ FURTHER DIRECTIONS


For any a,b,c∈ℤ^+, we can define an analog to VW^×_3(n) by considering the equation ax+by=cz instead of x+y=2z.  (Assume p is greater than a, b, and c.) The bound from Theorem <ref> stays the same if a+b=c and goes down to n^4+5 otherwise.  But as suggested by the data in Figure <ref>, these bounds are not tight.  How does the choice of a, b, and c affect the growth rate of the corresponding Van der Waerden-like number? Clearly VW^×_3(n) is not monotonic, but it appears to bounce above and below some “average” polynomial growth rate. Will that growth rate vary with the choice of  a, b, and c? Does it depend on whether a+b=c only?



§ ACKNOWLEDGEMENTS


The author wishes to thank Andrew Shallue and Valentin Andreev for many productive conversations.




1

MR3213827
Noga Alon and Jean Bourgain.
Additive patterns in multiplicative subgroups.
Geom. Funct. Anal., 24(3):721–739, 2014.

MR3722263
Mei-Chu Chang.
Arithmetic progressions in multiplicative groups of finite fields.
Israel J. Math., 222(2):631–643, 2017.

Roth
K. F. Roth.
On certain sets of integers.
J. London Math. Soc., 28:104–109, 1953.

Schoen
Tomasz Schoen and Ilya D. Shkredov.
Additive properties of multiplicative subgroups of F_p.
Q. J. Math., 63(3):713–722, 2012.




