Maximize $f(0)+\cdots+f(n-1)$ subject to $f(x)f(y) + f(x+y) \leq 1$

Suppose $$f:\mathbf{N} \to [0,1]$$ satisfies $$f(x)f(y) + f(x+y)\leq 1\qquad(1)$$ for all $$x,y$$. Let $$d_n = \frac{1}{n} \sum_{x=0}^{n-1} f(x).$$ It is easy to prove that $$\limsup d_n \leq 1/\varphi,$$ where $$1/\varphi$$ is the positive solution to $$t^2+t=1$$. (Start with $$(1)$$, take an average and $$\limsup$$ in $$x$$, then in $$y$$.)

What's interesting is that it does not seem nearly so easy to bound $$d_n$$, without the $$\limsup$$, independently of $$f$$. Is it true that $$d_n \leq 1/\varphi + o(1),$$ where the $$o(1)$$ is independent of $$f$$?

This does seem to be true numerically. In fact it may even be that $$f \equiv 1/\varphi$$ is the unique maximizer of $$d_n$$ for each $$n$$.

• To clarify your final comment, are you saying that numerics suggest that $d_n\leq 1/\phi$ might be true for all $n$ (i.e. your conjecture holds even without the $o(1)$ term). – Thomas Bloom Dec 22 '18 at 18:49
• I understand the question to be: does $\max_f (d_n(f)-1/\phi)$ converge to 0, where the maximum is taken over all functions $f$ satisfying the constraint. – Anthony Quas Dec 22 '18 at 18:58
• Probably the arithmetic regularity lemma can be used to reduce the asymptotic problem to the continuous problem (in which $f$ now lives in $[0,1]$ rather than ${\bf N}$, and the goal is to get the best upper bound for $\int_0^1 f$). – Terry Tao Dec 22 '18 at 19:14
• The linearisation around $1/\varphi$ is then a good test problem. If $g: [0,1] \to {\bf R}$ is such that $\frac{1}{\varphi} g(x) + \frac{1}{\varphi} g(y) + g(x+y) \leq 0$ whenever $x,y,x+y \in [0,1]$, does it follow that $\int_0^1 g \leq 0$? – Terry Tao Dec 22 '18 at 19:15
• @TerryTao Yes, $\int g \leq 0$. Pick the largest $z\leq 1$ such that $g(z) > 0$ (if none exists, all is well). Then $g(x) + g(z-x) < 0$ for all $x \leq z$. Now average over $x \leq z$. But does this help? – Sean Eberhard Dec 22 '18 at 19:47

This system seems simple enough to throw to a CAS or some optimizer for small $$n$$. The inequalities are sequential: once you have understood behaviour for $$n$$, you can add a few more constraints for $$n+1$$ and try to understand the expanded system. To illustrate, I use $$x_n$$ in place of $$f(n)$$.

The first round is to maximize $$x_0$$ subject to $$x_0^2 + x_0 \leq 1$$. This is solved by the original poster and results in $$x_0 = 1/\phi$$.

The next round ($$n=2$$) adds the constraint equivalent to $$x_{n-1} \leq 1/(1+x_0)$$, and a little calculus and checking of boundary conditions gives $$x_1 + x_0$$ is maximized at $$x_1=x_0=1/\phi$$.

With each increase of $$n$$, the additional constraints are of the form $$x_n \leq 1-x_j x_{n-j}$$. However, we can ignore those constraints and focus on maximizing $$x_0 + x_n$$, which again we get with $$x_0=x_n=1/\phi$$. So I am guessing $$1/\phi$$ is the best you can do for the average value. (This does not quite work. However, if you get a value early on that approaches $$1/\phi$$, then this impacts later values. More work needs to be done.)

Here is some more work. Let us suppose we have $$n$$ least that $$x_n \gt 1/\phi$$. Then we have all the $$x_i \it 1/\phi$$ for all $$0 \leq i \lt n$$, and we know by above that the sum of the first $$n+1$$ variables is at most $$(n+1)/\phi$$. In particular, if $$x_n=1/\phi + \epsilon$$, then $$x_0 \lt 1/\phi \lt \epsilon$$.

If we now consider $$x_j = 1/\phi - \delta$$ and $$x_{n-j} = 1/\phi - \gamma$$, the relevant inequality gives $$\phi\epsilon \lt \gamma + \delta$$, so for $$n \gt 2$$ we have the sum is less than $$(n+1)/\phi$$ by at least $$(\phi -1)\epsilon$$, and this is magnified for all $$\lfloor n/2 \rfloor$$ pairs. It remains to study the case when $$x_1$$ and perhaps when $$x_2$$ are greater than $$1/\phi$$.

Update 2018.12.28

This argument is pretty simple, and suggests that something similar might work for $$f$$ over lower bounded subsets of the rationals or reals.

One sees that constant $$f$$ with value $$f \leq 1/\phi$$ satisfies the system of inequalities, so the best we can hope for is that $$d_n \leq c=1/\phi$$. I will recoordinatize and set $$e_n = f(n) - c$$, and use $$c$$ to simplify the TeX. We have $$cc + c = 1$$ and can rewrite the functional relation as $$e_j(c + e_{n-j})+ ce_{n-j} + e_n \leq 0$$.

We will be interested in showing the sum of the $$e_j$$ is at most 0. Towards that we rewrite the inequality as $$e_{n-j} + e_n \leq e_j(-c - e_{n-j}) + (1 - c)e_{n-j}$$. If all the $$e_k$$ are nonpositive, we are done. Otherwise, pick $$j$$ least with $$e_j \gt 0$$, and let $$n\geq j$$ be least $$n$$ with $$e_n \gt 0$$. Then the first form of the equality will imply $$e_{n+j} \lt 0$$, and the second form shows $$-c \leq e_{n-j} \lt e_{n-j} + e_n \lt 0$$.

Now let $$j$$ be least with $$e_j \gt 0$$. For every $$n$$, either $$e_n \leq 0$$ or else $$e_{n-j} + e_n\lt 0$$. This implies that the finite sum $$e_0 + e_1 + \cdots + e_n \leq 0$$ for all choices satisfying all the inequalities.

Gerhard "That's How I See It" Paseman, 2018.12.22.

• Thanks for your comments. Indeed I put the system through a generic optimizer before posting the question (viewable here: colab.research.google.com/drive/…). But I'm afraid I don't quite follow the details of your strategy for making this into a proof. – Sean Eberhard Dec 23 '18 at 10:34
• I am trying to show that the average is at most 1/phi. This is clear for n=1 and n=2. For n=3 at most one of the x's can be greater than 1/phi, and use the n=2 case to show the average is below. For larger n, the post above shows that if only the last x is greater than 1/phi, then the average is below 1/phi. It remains to handle the case when two or more x are above 1/phi, which I believe can be done. Gerhard "Still Doing Calculations With Epsilon" Paseman, 2018.12.23. – Gerhard Paseman Dec 23 '18 at 16:41
• I think I have it now. The first variable that is greater than 1/phi affects the other variables, and allows one to partition the other variables into subsums which average less than 1/phi each. Gerhard "Will Fill In Details Later" Paseman, 2018.12.28. – Gerhard Paseman Dec 28 '18 at 13:44
• I don't follow how your "either $e_n \leq 0$ or $e_{n-j} + e_n < 0$" condition implies $e_0 + \cdots + e_n \leq 0$. E.g., if $j = 1$ and $e = (.1, -.11, .1)$? I think I must be missing something... – Sean Eberhard Dec 30 '18 at 8:39
• If you index from 0, your vector e does not satisfy the inequality. $e_0 + e_j \leq 0$ holds for every $j$. If $e_1$ and $e_n$ are positive, we have $e_{n-1} + e_n$ is negative. Now either $e_1$ is non positive, or else we can start with $k=n$ and build up the sum(and decrement $k$ by one or by two) to show it is negative, adding either nonpositive $e_k$ or negative $(e_{k-1} + e_k)$ to get the whole sum is non positive. Gerhard "Nothing Up My Sleeve, Presto!" Paseman, 2018.12.30. – Gerhard Paseman Dec 30 '18 at 16:42

Gerhard Paseman's solution is correct, and shows that $$f \equiv 1/\phi$$ is the unique maximizer of $$d_n$$ for each $$n\geq 0$$. Just reproducing here in as few words as I can, for the purpose of succinctness.

Let $$c = 1/\varphi$$ be the positive solution to $$c^2 + c = 1$$. Let $$m\geq0$$ be minimal such that $$f(m) \geq c$$ (if there is no such $$m$$ then we can go home). From now on, the only thing we will use is

$$f(x) c + f(x+m) \leq 1. \qquad(*)$$

If $$m = 0$$ this immediately implies $$f(x) \leq c$$ for all $$x$$, so assume $$m>0$$.

Claim: For any $$i < m$$ and any $$k \geq0$$, the sum of $$f$$ over the arithmetic progression $$\{i, i+m, i+2m, \dots, i+(k-1)m\}$$ is at most $$kc$$. The inequality is strict for $$k > 0$$.

Prove this and we're done, by partitioning $$\{1, \dots, n\}$$ into such progressions.

Proof: Use induction on $$k$$. The case $$k=0$$ is trivial. The case $$k=1$$ follows from $$i < m$$. For $$k > 1$$, note by induction and $$(*)$$ that $$f(i) + \cdots + f(i + (k-3)m) \leq (k-2)c,$$ $$f(i) + \cdots + f(i + (k-2)m) < (k-1)c,$$ $$f(i + (k-2)m) c + f(i+(k-1)m) \leq 1.$$ Add these together with weights $$c$$, $$c^2$$, and $$1$$.