11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Thomas Bloom Dec 22 '18 at 18:49
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Dec 22 '18 at 18:58
  • $\begingroup$ 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$). $\endgroup$ – Terry Tao Dec 22 '18 at 19:14
  • $\begingroup$ 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$? $\endgroup$ – Terry Tao Dec 22 '18 at 19:15
  • 1
    $\begingroup$ @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? $\endgroup$ – Sean Eberhard Dec 22 '18 at 19:47
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sean Eberhard Dec 23 '18 at 10:34
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Dec 23 '18 at 16:41
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Dec 28 '18 at 13:44
  • $\begingroup$ 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... $\endgroup$ – Sean Eberhard Dec 30 '18 at 8:39
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Dec 30 '18 at 16:42
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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