13
$\begingroup$

$\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$).

$\endgroup$
6
  • 2
    $\begingroup$ Just a comment: since any such map has image in a finite-dimensional $\mathbb{Q}$-subvector space in $\mathbb{R}$, and any such subspace surjects onto $\mathbb{Q}$, we can postcompose to get a map to the rationals with no more pairs violating addivity. By multiplying with the common denominator, we can further reduce to a map $\mathbb{F}_p\rightarrow\mathbb{Z}$. $\endgroup$ Jan 26, 2018 at 12:07
  • $\begingroup$ @AchimKrause: In fact, my functions $\phi_i$ are rational-valued by the virtue of the problem I need this for. $\endgroup$
    – Seva
    Jan 26, 2018 at 15:05
  • $\begingroup$ How is $p$ being prime relevant to the problem? $\endgroup$
    – Qfwfq
    Jan 26, 2018 at 22:22
  • $\begingroup$ @Qfwfq: Other finite fields can be fine, too, but I do not care about generalizations. $\endgroup$
    – Seva
    Jan 27, 2018 at 7:11
  • $\begingroup$ I was thinking about the fact that you seem to use only the additive structure, so any cyclic group would do as fine. $\endgroup$
    – Qfwfq
    Jan 27, 2018 at 13:40

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ The MO recommendation is to avoid comments like "thanks", and yet: THANKS! $\endgroup$
    – Seva
    Jan 26, 2018 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.