Define the function $e(x) = e^\frac{2\pi x i}{p}.$ Let $\chi$ be the characters (mod $p$), and write $e(f) = \sum_{\chi} \hat{f}_\chi \chi.$ It is easy to check that \[ p^2 e^\frac{200 \pi i}{p} \le \sum_{x, y} e(f(x+y) - f(x) - f(y)) = p^2 \sum_{\chi} \left( \overline{\hat{f}_\chi} \right) |\hat{f}_\chi|^2 \le p^2 \cdot \max_\chi \text{Re}(\hat{f}_\chi) \]by the condition and Parseval's identity. Therefore, there is a $\chi$ (say $\chi(x) = e(mx)$) s.t. \[ \frac{1}{p} \sum_x \cos\left(\frac{2\pi(f(x) - mx)}{p} \right) = \text{Re}(\hat{f}_\chi) \ge \text{Re}\left( e^\frac{200 \pi i}{p} \right). \] Assume that $|f(x) - mx| \ge 1000$ for some $x$. It is easy to check that for any pair $(k, x-k)$ that we have that \[ \cos(f(k) - mk) + \cos(f(x-k) - m(x-k)) \le \text{Re}\left(e^\frac{400\pi i}{p} \right) \]by the initial condition ($|f(x) - f(k) - f(x-k)| < 100$) and that $\cos(f(x) - mx) \le \text{Re}\left( e^\frac{2000\pi i}{p} \right)$. Summing over all $k$ gives a contradiction.

mathocean97 wrote: Define the function $e(x) = e^\frac{2\pi x i}{p}.$ Let $\chi$ be the characters (mod $p$), and write $e(f) = \sum_{\chi} \hat{f}_\chi \chi.$ It is easy to check that \[ p^2 e^\frac{200 \pi i}{p} \le \sum_{x, y} e(f(x+y) - f(x) - f(y)) = p^2 \sum_{\chi} \left( \overline{\hat{f}_\chi} \right) |\hat{f}_\chi|^2 \le p^2 \cdot \max_\chi \text{Re}(\hat{f}_\chi) \]... Nice idea. As I see it, you consider the function: $g(x) := e^\frac{2\pi i f(x)}{p}$ and then write $g = \sum_{\chi} \hat{g}_\chi \chi.$ (by Foutier inversion) Could you elaborate why does it hold: $$\sum_{x, y} \frac{g(x+y)}{g(x)g(y)} = p^2 \sum_{\chi} \left( \overline{\hat{g}_\chi} \right) |\hat{g}_\chi|^2$$

Notice that $|f(0)|< 100$, since $|f(0+0)-f(0)-f(0)|< 100$. Let us consider the function $f_1(x) := f(x)-f(1)\cdot x$. It also satisfies that almost additive condition. Moreover, $|f_1(x+1)-f_1(x)|=|f(x+1)-f(x)-f(1)|< 100$. We can assume $p>1000$ since the claim is trivial for small $p$. It is convenient to imagine $f_1$ as taking integer values, starting from $f_1(0)\in (-100,100)$ and at every step jumping at most $100$ units up or down, that's if for example $f_1(x)=p-1, f_1(x+1)=50$ , we think of it as $f_1(x+1)=p+50$ , which of course is the same $\pmod{p}$. Thus, going this way we obtain $f_1(p)=kp+f_1(0)$, where $k\in(-100,100)$. Let us set $f_2(x) := f_1(x)-kx$. Then $f_2$ is also "almost additive", that's: $|f_2(x+y)-f_2(x)-f_2(y)|< 100$. It also holds $|f_2(x+1)-f_2(x)|< 200\,,\, |f_2(p)|=|f_1(0)|<100$. We will prove $|f_2(x)|< 100$. Let $|f_2(x_0)| := \max |f_2(x)|$ and suppose $f_2(x_0)>0$, the other case is similar. Arguing by contradiction, assume $f_2(x_0)\geq 100$. For $j=1,2,\dots,x_0$ we have: $$f_2(x_0+j) = f_2(x_0)+f_2(j) +\varepsilon_j$$where $\varepsilon_j\in(-100,100)\,,\,j=1,2,\dots,x_0$. For $j=x_0$ , we get $f_2(2x_0)\geq f_2(x_0)+1$. (The reason behind is $f_2(x_0+j)$ cannot jump too much when $j$ runs from $1$ to $x_0$). Thus, we get a contradiction. Since $f_2(x)=f(x)-(f(0)+k)x$ , the result follows.

wow , Dear dgrozev welcome back

dgrozev wrote: mathocean97 wrote: Define the function $e(x) = e^\frac{2\pi x i}{p}.$ Let $\chi$ be the characters (mod $p$), and write $e(f) = \sum_{\chi} \hat{f}_\chi \chi.$ It is easy to check that \[ p^2 e^\frac{200 \pi i}{p} \le \sum_{x, y} e(f(x+y) - f(x) - f(y)) = p^2 \sum_{\chi} \left( \overline{\hat{f}_\chi} \right) |\hat{f}_\chi|^2 \le p^2 \cdot \max_\chi \text{Re}(\hat{f}_\chi) \]... Nice idea. As I see it, you consider the function: $g(x) := e^\frac{2\pi i f(x)}{p}$ and then write $g = \sum_{\chi} \hat{g}_\chi \chi.$ (by Foutier inversion) Could you elaborate why does it hold: $$\sum_{x, y} \frac{g(x+y)}{g(x)g(y)} = p^2 \sum_{\chi} \left( \overline{\hat{g}_\chi} \right) |\hat{g}_\chi|^2$$ Sorry, good catch! I think the basic idea goes through despite there being some serious computation issues. First of all, what I really should be using is not $f(x+y) - f(x) - f(y)$ and instead $f(x+y) + f(-x) + f(-y).$ But we can still show $|f(x+y) + f(-x) + f(-y)| < 300$ by using triangle inequality a couple of times. Now repeat the above argument instead with $f(x+y) + f(-x) + f(-y)$ in place. I'll post an edited version below.

Note: This is essentially the same as above, except with the necessary edits. Define the function $e(x) = e^\frac{2\pi x i}{p}.$ Let $\chi$ be the characters (mod $p$), and write $e(f) = \sum_{\chi} \hat{f}_\chi \chi.$ By triangle inequality, we can easily show that $|f(x+y) + f(-x) + f(-y)| < 300$. It is easy to check that \[ p^2 e^\frac{600 \pi i}{p} \le \sum_{x, y} e(f(x+y) + f(-x) + f(-y)) = p^2 \sum_{\chi} \left( \overline{\hat{f}_\chi} \right) |\hat{f}_\chi|^2 \le p^2 \cdot \max_\chi \text{Re}(\hat{f}_\chi) \]by the condition and Parseval's identity. Therefore, there is a $\chi$ (say $\chi(x) = e(mx)$) s.t. \[ \frac{1}{p} \sum_x \cos\left(\frac{2\pi(f(x) - mx)}{p} \right) = \text{Re}(\hat{f}_\chi) \ge \text{Re}\left( e^\frac{600 \pi i}{p} \right). \] Assume that $|f(x) - mx| \ge 1000$ for some $x$. It is easy to check that for any pair $(k, x-k)$ that we have that \[ \cos\left(\frac{2\pi(f(k) - mk)}{p}\right) + \cos\left(\frac{2\pi(f(x-k) - m(x-k))}{p} \right) \le \text{Re}\left(e^\frac{800\pi i}{p} \right) \]by the initial condition ($|f(x) - f(k) - f(x-k)| < 100$) and that $\cos(f(x) - mx) \le \text{Re}\left( e^\frac{2000\pi i}{p} \right)$. Summing over all $k$ gives a contradiction.

@dgrozev what if f_2 is unbounded?

kmdngdng wrote: @dgrozev what if f_2 is unbounded? The domain of $f$ and $f_2$ is $\mathbb{F}_p.$ So they cannot be unbounded.