4
$\begingroup$

so the problem I'm interested in is to show that all sufficiently large finite fields contain an arithmetic progression of 9 distinct perfect squares.

A professor in my department had some previous results from which this should follow. I asked her to help me understand her work and she kindly wrote out and emailed me a calculation involving characters to this end. But due to logistical constraints, she isn't able to explain the calculation to me in person and I'm struggling to understand it. I was hoping someone here could help me get my head around what's going on.

My bird's eye view understanding so far is just that we take a particular character on our finite field (and the subgroup of squares?), take a particular sum of character evaluations and somehow a result from Weil gives us a bound on the order of finite fields ensuring the desired arithmetic progression. I know that's not much to start with. I haven't touched a character since my undergrad in 2018.

There was also a hand-writing challenge as it seemed there were two or more different $\chi$'s in the calculation (one a character and another a field element) along with an $x$ (polynomial indeterminate). So I took the liberty of changing the field element "$\chi$" to $b$. Besides that, what follows is my best attempt to faithfully TeX up what she sent me. Thanks in advance for any guidance.

$\chi=$ mult char of order $m$

$f\in \mathbb F_q[x], f\not=g^m, \forall g\in \mathbb F_q[x]$

$d=$ # of distinct roots of $f$ in $\overline{\mathbb F}_q$

$\Rightarrow \Big|\sum_{b\in\mathbb F_q}\chi\big(f(b)\big)\Big|\le (d-1)\sqrt{q}$ (Weil)

$G=(\mathbb F_p^*)^2<\mathbb F_p^*=\langle a\rangle, |G|=\frac{p-1}{2}$

$\hat {\mathbb F}_p^*=\langle y\rangle, \text{ where } y:a\rightarrow \omega, \omega=e^{2\pi i/(p-1)}$

$1_G=\frac{1}{2}(\chi_0+\chi),\text{ where } \chi_0=1, \chi=y^{\frac{p-1}{2}}\quad (1.2), (1.3)$

WTS $\sum_{b \in \mathbb F_p}1_G(1+b)1_G(1+2b)...1_G(1+8b)\not=0\quad (1.1)$

$=_{(1.2)}\Big(\frac{1}{2}\Big)^8(p+A),\quad (1.4)$

where $A=\sum_b \Big(\sum_{k=1}^8\chi(1+kb)+\sum_{k_1<k_2}\chi\big((1+k_1b)(1+k_2b)\big)+\sum_{k_1<k_2<k_3}\chi\big((1+k_1b)(1+k_2b)(1+k_3b)\big)+...+\chi\big((1+b)(1+2b)...(1+8b)\big)\Big)$

$|A| \le 8\cdot \binom{8}{4} \max\Big|\sum_{b\in\mathbb F_p}\chi\big(f(b)\big)\Big|,$ where $f$ has distinct roots, $\deg f\le 8$

$\le_{\text{Weil}} 8\cdot \binom{8}{4}\cdot 7\cdot \sqrt{p}=3920\sqrt{p}$

$\Rightarrow (1.4) > \Big(\frac{1}{2}\Big)^8(p-769\sqrt{p})$

$\Rightarrow (1.1)\not=0$ when $p>769^2$

$\endgroup$
5
  • $\begingroup$ Presumably you have a constraint on the characteristic :-) After all, in characteristic $p$ every arithmetic progression loops back to itself after $p$ steps. $\endgroup$ Commented Sep 4 at 7:51
  • 1
    $\begingroup$ @Jyrki, $q$ disappears from the calculation early on, thereafter only $p$ appears, and the end result is given as $p>769^2$, so I think that takes care of your comment. $\endgroup$ Commented Sep 4 at 7:58
  • $\begingroup$ Ok @Gerry, didn't look carefully. My comment was just a knee-jerk reaction saying that the claim in boldface is trivially wrong for all the fields of characteristic $2,3,5$ or $7$, so size alone won't do. Wonder why she even mentions characters other than the Legendre character? $\endgroup$ Commented Sep 4 at 8:08
  • $\begingroup$ There is also the trivial observation that all the elements of $\Bbb{F}_q$ are squares of elements of $\Bbb{F}_{q^2}$. So if $q$ is a square, the question is trivial as long as $p>7$. Surely, that is a non-interesting case, and doesn't cover as much ground as you would like to :-) $\endgroup$ Commented Sep 6 at 12:33
  • $\begingroup$ maybe worth mentioning that Szemerédi's theorem would take care right away of the case of prime $q$... probably the character method gives much better estimates $\endgroup$ Commented Sep 7 at 15:37

1 Answer 1

Reset to default
6
$\begingroup$

I think what she is doing comes from the following. At least this is how I would approach the main problem (when armed with the theory of characters and Weil's bound), but may be I misunderstood something? Here comes, anyway! Let $q=p^m$, $p$ a prime, $K=\Bbb{F}_q$.

  • An arithmetic progression $a,a+d,a+2d,\ldots, a+8d$ of elements of $K$ consists entirely of squares if and only if the same holds for the progression $1,1+(d/a),\ldots,1+8(d/a)$. So w.l.o.g we can assume that the progression starts from $1$. Following your convention, I denote by $b=d/a$ the constant difference between consecutive terms of the progression.
  • The entries of that progression are distinct if and only if $p>7$. Otherwise $a=a+pd$.
  • Let $\chi:K\to \{0,\pm1\}$ be the Legendre character defined to take the value $+1$ at the squares $\neq0$, the value $-1$ at non-squares, and $0$ at zero. This is a multiplicative character.
  • So the product $$P(b):=\prod_{j=1}^8(1+\chi(1+jb))$$ is zero whenever at least one of the elements $1+jb$, $0<j<9$, is a non-square. Otherwise $P(b)$ is a positive integer (usually $2^8$, but may be $2^7$, if $1+jb=0$ for some $j$).
  • So if we can show that $$\sum_{b\in K^*}P(b)>0,$$ it follows that at least one of the progressions $1,1+b,\ldots,1+8b$ consists of squares only.
  • Denote $S=\{1,2,\ldots,8\}$. For every subset $T\subseteq S$ define the polynomial $$f_T(x)=\prod_{j\in T}(1+jx)\in K[x].$$ Because $\chi(xy)=\chi(x)\chi(y)$ for all $x,y\in K$ we see that $$ \begin{aligned} \sum_{x\in K^*}P(x)&=\sum_{x\in K^*}\prod_{j\in S}(1+\chi(1+jx))\\ &=\sum_{x\in K^*}\left(1+\sum_{T\subseteq S,T\neq\emptyset}\chi(f_T(x))\right)\\ &=(q-1)+\sum_{T\subseteq S,T\neq\emptyset}\sum_{x\in K^*}\chi(f_T(x)). \end{aligned} $$ (see the bottom of this post for an explanation of the second step). The idea is then that by Weyl's bound for all non-empty $T$ $$ \sum_{x\in K^*}\chi(f_T(x))\ge -(|T|-1)\sqrt q.\qquad(*) $$ Then I would sum the bounds $(*)$ over all $2^8-1$ choices of $T$, and check what I need to assume about $q$ to conclude that the above lower bound $$ \sum_{x\in K^*}P(x)\ge (q-1)-\left(\sum_{T\subseteq S}(|T|-1)\right)\sqrt q $$ is positive. That sum over $T$ is a constant, so this happens when $q$ is large enough (and you still also need $p>7$).

It's been a while since I last looked at problems like this, but you do arrive at some lower bound for $q$ in this way.

===

So expansions like (a toy example when $S=\{1,2\}$, so arithmetic progressions of length three only): $$ \begin{aligned} \prod_{j=1}^2(1+\chi(1+jx))&=(1+\chi(1+x))(1+\chi(1+2x))\\ &=1+\chi(1+x)+\chi(1+2x)+\chi((1+x)(1+2x))\\ &=1+\chi(f_{\{1\}}(x))+\chi(f_{\{2\}}(x))+\chi(f_{\{1,2\}}(x)) \end{aligned} $$ are the key allowing us to apply the Weil bound to all the non-trivial terms in the last row. It is a bit messier when $j$ ranges over $\{1,2,\ldots,8\}$ instead of just $\{1,2\}$ as in the toy example.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.