Near-linear mappings from $\mathbb F_p$ to $\mathbb R$

Question

$\newcommand{\F}{{\mathbb F}}$ $\newcommand{\R}{{\mathbb R}}$ $\renewcommand{\phi}{\varphi}$

Let $p\ge 5$ be a prime.

If the functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ satisfy $\phi_1(x)+\phi_2(y)=\phi_3(x+y)$ for all pairs $(x,y)\in\F_p^2$, then they are constant functions. The easiest way to see this is by comparing the images $A_i:=\mathrm{Im}(\phi_i)$: $$ A_1+A_2 \subseteq A_3,\ A_3-A_1\subseteq A_2,\ A_3-A_2\subseteq A_1, $$ whence $|A_1|=|A_2|=|A_3|=1$.

Given that $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$ are non-constant, what is the largest possible number of pairs $(x,y)\in\F_p^2$ satisfying $$ \phi_1(x)+\phi_2(y)=\phi_3(x+y)? \tag{$\ast$} $$ Equivalently, what is the smallest possible number of pairs $(x,y)\in\F_p^2$, for all choices of the non-constant functions $\phi_1,\phi_2,\phi_3$, such that ($\ast$) fails to hold?

If $u,v,w\in\F_p$ are pairwise distinct and $w\ne u+v$ then, letting $$ \phi_1=1_{\{u\}},\ \phi_2=1_{\{v\}},\ \phi_3=1_{\{w\}} $$ (the indicator functions of the corresponding singletons), we have $3p-5$ pairs $(x,y)$ violating ($\ast$); is this the worst case?

Is it true that for any non-constant functions $\phi_1,\phi_2,\phi_3\colon\F_p\to\R$, there are at least $3p-5$ pairs $(x,y)\in\F_p^2$ with $$ \phi_1(x)+\phi_2(y) \ne\phi_3(x+y)? \tag{$\circ$}$$

What I can show, in two different ways, is that there are at least $p-1$ pairs $(x,y)$ satisfying ($\circ$).

Answer 1

Yes, for $p$ sufficiently large.

Assume that $\phi_1,\phi_2,\phi_3$ satisfy this condition for at most $3p-5$ values of $x,y$.

Hence for each $a$, all but at most $6p-10$ pairs $(x,y)$ satisfy

$$\phi_1(x+a) + \phi_2(y) - \phi_3(x+a+y) = 0 = \phi_1(x) + \phi_2(y+a)- \phi_3(x+a+y)$$

in other words

$$\phi_1(x+a) - \phi_1(x) = \phi_2(y+a) - \phi_2(y)$$

Now when we have the equation $$F(x)=G(y)$$ for all but at most $6p-10$ pairs $(x,y)$, then for some value of $y$ the equation must be satisfied for all but at most $6$ values of $x$.

So for all $a \in \mathbb F_p$, there is some $c_a$ with $\phi_1(x+a) - \phi_1(x) = c_a$ for all but at most $6$ values of $x$.

Now given $a,b$ there are at least $p-18$ values of $x$ where $\phi_1(x+a)-\phi_1(x) = c_a$, $\phi_1(x+a+b)-\phi_1(x+a)=c_b$, $\phi_2(x+a+b)-\phi_1(x) = c_{a+b}$, and hence as soon as $p>18$, $c_{a+b}=c_a+c_b$, $c$ is a homomorphism $\mathbb F_p \to \mathbb R$ and hence vanishes.

Hence for all $a$ in $\mathbb F_p$, $\phi_1(x+a)= \phi_1(x)$ for all but $6$ values of $x$. Hence $\phi_1(x)=\phi_1(y)$ for all but $6p$ values of $x,y$. Hence for some $y$, $\phi_1(x)=\phi_1(y)$ for all but $6$ values of $x$.

Applying the same logic to $\phi_1$ and $\phi_2$, there are constants $A,B,C$ such that $\phi_1(x)=A, \phi_2(x)=B,\phi_3(x)=C$, each with at most $6$ exceptions. So as soon as $p^3- 18 p^2 > 3p-5$, $A+B=C$.

Now let $\alpha,\beta,\gamma$ be the number of exceptions to these equations. There are $(\alpha+\beta+\gamma)p - (\alpha\beta+ \alpha\gamma+\beta\gamma)$ pairs $x,y$, where exactly one of $x,y,x+y$ is an exception, and for none of these pairs is $\phi_1(x)+\phi_2(y)=\phi_3(x+y)$. For $p$ sufficiently large, this is minimized by minimizing $\alpha+\beta+\gamma$, which is minimized when $\alpha=\beta=\gamma=1$, since all are at least one.

But in this case, the best we can do is your example.