I am reading Behrend's On Sets of Integers Which Contain No Three Terms in Arithmetical Progression.
For integers $d\ge 2$, $n\ge 2$, and $k\le n(d-1)^2$, the author defines $S_k(n,d)$ as the set of all numbers of the form $$A = \sum_{i=0}^{n-1} a_{i+1} (2d-1)^{i}$$ where $a_{i+1} \in \Bbb Z$ satisfy $0\le a_{i+1} < d$, and $\sum_{i=1}^n a_i^2 = k$. Furthermore, the author goes on to call the quantity $\sqrt{\sum_{i=1}^n a_i^2}$ as $\operatorname{norm}(A)$.
Is this really a norm, though? What properties does it satisfy? For instance, one would like $$\operatorname{norm}(A+B) \le \operatorname{norm}(A) + \operatorname{norm}(B)$$ but there is no guarantee that $A+B$ also lies in $S_k(n,d)$. To get past this difficulty, one could define $$\operatorname{norm}(A) = \sqrt{\sum_{i=1}^m a_i^2}$$ for any number $A$ expressible as $$A = \sum_{i=0}^{m-1} a_{i+1} (2d-1)^{i}$$ where we place no restrictions on $m$ besides $m\in \Bbb N \cup \{0\}$, and the $a_{i+1}$'s still satisfy $0\le a_{i+1} < d$. Would this induce a bonafide norm on some superset of $S_k(n,d)$?
I ask this question to understand Behrend's construction of a $3$-AP free set, namely $S_k(n,d)$. The proof in the paper goes as follows. We let $A, A', A''$ satisfy $A+A' = 2A''$. The goal is to show $A=A'=A''$. The paper says:
- $$\operatorname{norm}(A+A') = \operatorname{norm}(2A'') = 2\sqrt{k}$$ for which (i) it must make sense to compute the norm of $A+A'$, and (ii) $\operatorname{norm}(kA) = k\operatorname{norm}(A)$ should hold, where $k\in \mathbb N$.
- $$\operatorname{norm}(A+A') \le \operatorname{norm}(A) + \operatorname{norm}(A')$$ which also raises similar concerns as in $(1)$ above.
I would appreciate it if someone could throw some light on Behrend's construction, particularly the so-called "norm" in the picture. Thanks!
Edit: Perhaps one of the biggest red flags of this "norm" is that $S_k(n,d)$ is not even a vector space! However, can we embed $S_k(n,d)$ into an appropriate vector space?
I'll explain what I think is going on in a little bit of generality. Suppose $N = m^n$ for some number $m$, and let $I = \{0,1,\dots,N-1\}$. Each $A\in I$ can be expressed uniquely in base $m$ as $$ A = a_0 + a_1m + \dots + a_{n-1}m^{n-1} $$ where each of the digits $a_i$ satisfies $0\le a_i < m$. Since this representation is unique, we can associate to each $A\in I$ a corresponding vector $$ v_A = (a_0,a_1,\dots,a_{n-1})\in\mathbb Z^n. $$ The "norm" of a number $A\in I$ is now seen to be the same as the Euclidean norm of the vector $v_A$. In particular, the "norm" of a number in $I$ is unambiguously defined in this way.
Now let $I_c$ be the set of numbers $A\in I$ with digits $0\le a_i < cm$, where $c$ is sufficiently small. As long as $c$ is sufficiently small, addition of the numbers in $I_c$ is equivalent to vector addition in the corresponding subset of $\mathbb Z^n$. That is, for any $A,A',A''\in I_c$ we have $A + A' = A''$ if and only if $v_A + v_{A'} = v_{A''}$.
Suppose we take $c = 1/2$, and $A,A'\in I_{1/2}$. Then $A+A'$ need not be a member of $I_{1/2}$, but the number $A+A'$ has all of its digits $a_i + a_i' < m$, so the vector $v_{A+A'}$ is still well-defined and even satisfies $v_{A+A'} = v_A + v_{A'}$, so \begin{align*} \operatorname{norm}(A+A') \le \operatorname{norm}A+\operatorname{norm}A' \end{align*} because the same holds true for the corresponding vectors.
Furthermore, if $A\in I_{1/2}$, then $2A\in I$, and $$ \operatorname{norm}2A = \|v_{2A}\| = \|2v_A\| = 2\operatorname{norm}A. $$ (In general, to be able to say $\mathrm{norm}\,kA = k\,\mathrm{norm}\,A$, we'd have to restrict to $A\in I_{1/k}$ for the left-hand side of the equality to be well-defined.)
Last notes: In Behrend's paper, the condition (i) is essentially restricting all of the numbers $A$ in $S_k(n,d)$ to lie in $I_{1/2}$. The numbers in $I_{1/2}$ that satisfy the condition (ii) in that paper are by definition $S_k(n,d)$, and they are essentially the numbers $A\in I_{1/2}$ whose corresponding vectors $v_A$ lie on the sphere of radius $\sqrt k$.
Lastly, I found this paper of Izabella Łaba and Michael Lacey helpful. See especially the beginning of Section 2.