5
$\begingroup$

There is an almost invisible, but significant difference between the question below and that recently answered by Boris Bukh.

Given a probability measure $\mu$ supported on a finite set $S\subset{\mathbb R}^2$, define $$ f(z):=\max\left\{\mu(x)\colon \frac{x+y}2=z,\ x,y\in S \right\}, \ z\in{\mathbb R}^2. $$ Now let $\bar\mu$ be the uniform probability measure supported on the same set $S$, and define $$ \bar f(z):=\max\left\{\bar\mu(x)\colon \frac{x+y}2=z,\ x,y\in S \right\},\ z\in{\mathbb R}^2. $$

Is it true that for any choice of the measure $\mu$, the total mass of $f$ is at least as large as the total mass of $\bar f$?

(Notice that $\bar f$ is actually a scaled indicator function of the set $\{(x+y)/2\colon x,y\in S\}$, and that the total mass of $\bar f$ is actually the doubling coefficient $|S+S|/|S|$.)

$\endgroup$

1 Answer 1

4
$\begingroup$

This is also false.

Let $S=A\cup B$ where $A$ is $\{0,1,\dotsc,n-1\}$ and $B$ is a subset of $\{n,n+1,\dotsc,2n\}$ of size $m\leq 4\sqrt{n}$ such that $B+B$ contains all the integers from $2n$ to $4n$. (We can take $B$ to be a union of all multiples of $\sqrt{n}$ and two suitable arithmetic progressions of step $1$.) Note that the mass of $\bar{f}$ is $\approx 4n\cdot (1/n)=4$. Consider the probability distribution that is uniform on $A$, and assigns zero (or nearly zero) weight to $B$. For such a distribution, we compute the total weight of $f$ to be $\approx 3n\cdot(1/n)+n\cdot 0=3$.

I am not sure what exactly you are trying to do, but it is extremely unlikely that an inequality of the approximate form that you seek exists. The reason is that it must behave well under disjoint unions, tensor products, and be stable under local perturbations. That is a lot to ask!

$\endgroup$
4
  • $\begingroup$ Computation fixed. The numbers up to $3n$ are in $A+B$, whereas numbers from $3n$ to $4n$ are not. $\endgroup$
    – Boris Bukh
    Aug 20, 2015 at 16:29
  • $\begingroup$ $B=[n,n-1+\sqrt{n}]\cup \{n+k\sqrt{n}:k=1,\ldots,\sqrt{n}$ is enough, isn't it ? That's $\#B=2\sqrt{n}$. Nice example! $\endgroup$ Aug 21, 2015 at 14:27
  • $\begingroup$ No, $B+B$ doesn't fill $[2n,4n]$. I can't see how adding two suitable arithmetic progressions of step 1 does... $\endgroup$ Aug 21, 2015 at 15:50
  • $\begingroup$ @JeanDuchon The two progressions of length $\sqrt{n}$ and step $1$ are situated at the beginning and at the end of $\{n,n+1,\dotsc,2n\}$. $\endgroup$
    – Boris Bukh
    Aug 21, 2015 at 15:53

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.