7
$\begingroup$

Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that maximizes $|B\cap A_1|\times\dots\times |B\cap A_n|$, where $|\cdot|$ denotes the length (i.e. Lebesgue measure). If there are many such $B$, we choose one arbitrarily.

Now, we shrink $A_1$ to $A_1'\subseteq A_1$, and choose $B'$ using the same procedure. Is it always true that $|B'\cap A_1'|\le |B\cap A_1|$?

If $A_1,\dots,A_n$ are disjoint finite unions, the answer is positive, as shown here.

$\endgroup$

3 Answers 3

2
+50
$\begingroup$

OK, it seems that this is a counterexample.

Take 8 disjoint segments $I_1,\dots,I_8$ of length 1. Take 8 sets $$ S_1=\{1,2,3\}, \quad S_1=\{4,5,6\}, \quad S_1=\{1,2,4\}, \quad S_1=\{1,2,5\}, \quad S_1=\{1,2,6\}, \quad S_1=\{1,3,4\}, \quad S_1=\{1,3,5\}, \quad S_1=\{1,3,6\}. $$ Say that $I_i$ lies in $A_j$ iff $j\in S_i$, otherwise $I_i$ and $A_j$ are disjoint. Finally, set $c=2$.

In this situation, the optimal $B$ is $I_1\cup I_2$. where the product equals $1$. This follows from the fact that $\sum_j |B\cap A_j|\leq 6$, since any point is covered by at most three of the $A_j$.

Now set $A_1’=A_1\setminus I_1$. Consider the quantities $$ x=\left|B’\cap\left(\bigcup_{i=3}^8 I_i\right)\right|, \quad y=|B’\cap I_2|. $$ Then, by AM—GM, $$ |B’\cap A_1’|\leq x, \quad \prod_{j=2}^3 |B’\cap A_j|\leq (x/2+2-x-y)^2, \quad \prod_{j=4}^6 |B’\cap A_j|\leq (x/3+y)^3, $$ and the equalities are achievable simultaneously. Hence, in the optimal case, we have $$ \prod_{j=1}^6|B’\cap A_j|=x(2-x/2-y)^2(x/3+y)^3 =\frac{6x\cdot (36-9x-18y)^2\cdot (4x+12y)^3}{6\cdot 18^2\cdot 12^3}. $$

So we seek for a maximizer $(x_0,y_0)$ of $$ f(x,y)= 6x\cdot (36-9x-18y)^2\cdot (4x+12y)^3 $$ under the conditions $x.y\geq 0$, $x+y\leq 2$. We claim that such a maximizer has $x_0\geq 24/17$, which provides $|B’\cap A_1’|>|B\cap A_1|=1$, as desired.

Indeed, we have $$ f\left(\frac{24}{17},\frac{10}{17}\right) =\frac{144}{17}\cdot \left(\frac{216}{17}\right)^5. $$ On the other hand, if $x\leq 24/17$, by AM—GM we have $$ f(x,y)\leq 6x\cdot\left(\frac{2(36-9x-18y)+3(4x+12y)}5\right)^5 =6x\cdot\left(\frac{72-6x}5\right)^5; $$ the right hand part is an increasing function for $0\leq x\leq 2$, so $$ f(x,y)\leq 6\cdot \frac{24}{17}\cdot\left(\frac{72-6\cdot 24/17}5\right)^5 = f\left(\frac{24}{17},\frac{10}{17}\right), $$ as desired.

$\endgroup$
1
  • $\begingroup$ It is possible to find the maximizer: for a fixed $x>24/17$, the maximum is attained at $y,=2-x$ I just did not want to type all this, sorry. (But my computations led to a different value of $x$ --- perhaps because of a mistake.) $\endgroup$ Nov 1, 2020 at 7:15
1
$\begingroup$

$\newcommand\om\omega\newcommand\Om\Omega\newcommand\de\delta$As in the linked answer, this problem on sets can be restated as the following problem on real numbers.

Let $\Om:=\{0,1\}^n$. For each $\om\in\Om$ and each $i\in[n]:=\{1,\dots,n\}$, let $\om_i$ denote the $i$th coordinate of the vector $\om$, so that $\om=(\om_1,\dots,\om_n)$.

For any $a=(a^\om)\in[0,\infty)^\Om$ and any $c\in[0,\sum_{\om\in\Om} a^\om]$, let $$B(a):=B_c(a):=\Big\{b=(b^\om)\in[0,\infty)^\Om\colon0\le b^\om\le a^\om\ \forall\om\in\Om,\sum_{\om\in\Om\setminus\{(0,\dots,0)\}}b^\om=c\Big\}.$$

Let $b(a)=b_c(a)$ be any maximizer of $$\pi(b):=\prod_{i=1}^n\sum_{\om\in\Om\colon\,\om_i=1}b^\om$$ over all $b\in B(a)$.

Take now any $u=(u^\om)\in[0,\infty)^\Om$ such that $u^\om\le a^\om$ for all $\om\in\Om$ with $\om_1=1$ and $u^\om=a^\om$ for all $\om\in\Om$ with $\om_1=0$. Let $b(u)=b_c(u)$ be any maximizer of $\pi(b)$ over all $b\in B(u)$. Does it then necessarily follow that $$\sum_{\om\in\Om\colon\,\om_i=1}b(u)^\om\le\sum_{\om\in\Om\colon\,\om_i=1}b(a)^\om?$$

In this restatement, for all $\om\in\Om$

  • $a^\om$ stands for $|A^\om|$, where $A^\om:=A_1^{\om_1}\cap\cdots\cap A_n^{\om_n}$ for $A=(A_1,\dots A_n)$ with $A_i\subseteq J$ for all $i\in[n]$, where $J$ is the segment in question; and, for $C\subseteq J$ and $\de\in\{0,1\}$, we let $C^\de:=C$ if $\de=1$ and $C^\de:=J\setminus C$ if $\de=0$;
  • $b^\om$ stands for $|B\cap A^\om|$.

We see that even the restated problem, in terms of real numbers, concerns maximizing the non-convex/non-concave function $\pi(\cdot)$ over a polytope of dimension $2^n-1$, defined by $2^{n+1}$ affine inequalities. Moreover, we need to compare solutions of two such problems. This seems hard! If someone can answer this question, it could be quite an instructive moment!

$\endgroup$
7
  • 1
    $\begingroup$ While instructive, this doesn't seem to be an answer. It seems like at least the last paragraph could be isolated as a comment, with a pointer to your answer for the details of the re-statement $\endgroup$
    – LSpice
    Oct 24, 2020 at 23:24
  • 2
    $\begingroup$ @LSpice : This is clearly far from a complete answer. What this post provides, as noted, is a restatement of the problem on sets as a problem on real numbers, which are simpler objects than sets. It is also clear that this restatement, while possibly of use, is far too long for a comment. Also, I used the phrase "an instructive moment" in reference to a hopefully possible complete answer. Finally, the answer linked in your comment does not really provide details on the above restatement. $\endgroup$ Oct 25, 2020 at 3:16
  • 1
    $\begingroup$ This clearly counts as a partial answer IMHO. $\endgroup$
    – Nik Weaver
    Oct 28, 2020 at 4:02
  • $\begingroup$ Not sure whether it matters much, but this is not an equivalent reformulation. Check what haoens when you shrink $A_1$ to $A_1'$: surely, $|A_2\cap A_1|$ decreases, but $|A_2\cap A_1^0|$ increases, which is not reflected here. $\endgroup$ Oct 30, 2020 at 10:42
  • $\begingroup$ @IlyaBogdanov : This depends on how you interpret the informal term "shrink". My interpretation was that whatever is removed from $A_1$ is also removed from $A_2,\dots,A_n$. With this interpretation, I think the reformulation is equivalent. Anyhow, it is straightforward to adjust this reformulation to your apparent interpretation. $\endgroup$ Oct 30, 2020 at 16:07
0
$\begingroup$

Great question, I also have a formulation, plus some observations.
Given a matrix $M$, find the vector $x$ such that $x\le \ell_i$ and $x\cdot1=c$ and $x$ maximizes $\Pi_i (M\cdot x)_i$.
Here each $x_i$ denotes the part of $B$ that falls in the intersection of some given $A$'s.
Equivalently, we could try to maximize $\Sigma_i \log (M\cdot x)_i$.
From Jensen's inequality, any two solutions $x$ give the same maximum.
Moreover, each $(M\cdot x)_i$ needs to be the same as well.

$\endgroup$

Your Answer

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