11
$\begingroup$

Question

Given $\lambda\in\mathbb{R}^+$, what is the smallest possible $c$ for which, given any measurable region $\mathcal{P}$ in the plane with measure $1$, there always exists a vector $\mathbf{v}$ with magnitude $\lambda$ so that the area shared between $\mathcal{P}$ and its translate by $\mathbf{v}$ is at most $c$?


Background

On this year's USA TSTST (a test that determines a group of about 30 people to take selection tests for the following year's USA team to the International Math Olympiad), there was an algebra/geometry/combinatorics hybrid problem that I found interesting:

Show that there is an absolute constant $c < 1$ with the following property: whenever $\mathcal P$ is a polygon with area $1$ in the plane, one can translate it by a distance of $\frac{1}{100}$ in some direction to obtain a polygon $\mathcal Q$, for which the intersection of the interiors of $\mathcal P$ and $\mathcal Q$ has total area at most $c$.

Essentially every solution can be boiled down to the following:

Step 1. For a given vector $\mathbf{v}\in \mathbb{R}^2$, define $f(\mathbf{v})=\mu\big(\mathcal{P}\cap(\mathcal{P}+\mathbf{v})\big)$, where $\mu(\cdot)$ is the area of a region, and $\mathcal{P}+\mathbf{v}$ consists of the points in $\mathcal{P}$ translated by $\mathbf{v}$.

Step 2. Prove $f(\mathbf{u}+\mathbf{v})\geq f(\mathbf{u})+f(\mathbf{v})-1$ and generalize it to

$$1-f\left(\sum_{i=1}^N \mathbf{v}_i\right)\leq \sum_{i=1}^N \left(1-f\left(\mathbf{v}_i\right)\right).$$

Step 3. Define, for real $t$,

$$I_t=\int_{0\leq ||\mathbf{v}||\leq t} f(\mathbf{v})\ d^2\mathbf{v} = \int_{0\leq ||\mathbf{v}||\leq t}\int_{\mathbf{x}\in \mathcal{P}} \mathbf{1}_{\mathcal{P}}(\mathbf{x}+\mathbf{v})\ d^2\mathbf{x}\ d^2\mathbf{v}.$$

We have

\begin{align} I_t&=\int_{\mathbf{x}\in \mathcal{P}} \int_{0\leq ||\mathbf{v}||\leq t}\mathbf{1}_{\mathcal{P}}(\mathbf{x}+\mathbf{v})\ d^2\mathbf{v}\ d^2\mathbf{x}\\ &=\int_{\mathbf{x}\in \mathcal{P}} \mu\left(\mathcal{P}\cap\big\{\mathbf{x}+\mathbf{v}\big|0\leq ||\mathbf{v}||\leq t\big\}\right)\ d^2\mathbf{x}\\ &\leq\int_{\mathbf{x}\in \mathcal{P}} 1\ d^2\mathbf{x} = 1. \end{align}

So, there must exist some $\mathbf{v}$ with $0\leq ||\mathbf{v}||\leq t$ that satisfies

$$f(\mathbf{v})\leq \frac{1}{\pi t^2}.$$

Step 4. Write this vector as

$$\mathbf{v}=\sum_{i=1}^{\lceil 100t\rceil}\mathbf{u}_i$$

where $||\mathbf{u}_i||=1/100$.

Step 5. We now have

$$1-\frac{1}{\pi t^2}\leq 1-f(\mathbf{v})\leq \sum_{i=1}^N (1-f(\mathbf{u}_i)),$$

so for some $i$ we must have

$$1-f(\mathbf{u}_i) \geq \frac{1}{\lceil 100t\rceil}\left(1-\frac{1}{\pi t^2}\right)$$

$$f(\mathbf{u}_i) \leq 1-\frac{1}{\lceil 100t\rceil}\left(1-\frac{1}{\pi t^2}\right).$$

As long as $t^2>1/\pi$, this gives us a working value of $c<1$. It is minimized at $t=0.98$, which gives

$$c\approx 0.99318.$$

More generally, if $\lambda$ is the length of our translate, this is minimized at the nearest integer multiple of $\lambda$ to $\sqrt{3/\pi}$, which gives

$$c\approx 1-2\lambda\sqrt{\frac{\pi}{27}}.$$

In particular, for large enough $\lambda$, this bound does nothing.


Progress

I've been able to improve the bound on $c$ given slightly in the following manner:

Assume, for all $||\mathbf{u}||=\lambda$, that $f(\mathbf{u})>1-\epsilon$. Then, for all vectors $\mathbf{v}$ of length $\leq n\lambda$, by writing $\mathbf{v}=\sum_{i=1}^n \mathbf{u}_i$ with $||\mathbf{u}_i||=\lambda$, we must have

$$1-f(\mathbf{v})\leq n\epsilon\implies f(\mathbf{v})\geq 1-n\epsilon.$$

Using (almost) our same integral as earlier and setting $t=N\lambda$, we have

$$\int_{\lambda< ||\mathbf{v}||\leq t} f(\mathbf{v})\ d^2\mathbf{v}\leq 1.$$

(we cannot start the integral at $0$ as vectors with magnitude $<\lambda$ cannot be represented as the sum of one vector with magnitude $\lambda$). However,

\begin{align} \int_{\lambda \leq ||\mathbf{v}||\leq N\lambda} f(\mathbf{v})\ d^2\mathbf{v} &= \sum_{k=2}^N \int_{(k-1)\lambda< ||\mathbf{v}|| \leq k\lambda} f(\mathbf{v})\ d^2\mathbf{v}\\ &\geq \sum_{k=2}^N \int_{(k-1)\lambda< ||\mathbf{v}|| \leq k\lambda} 1-k\epsilon\ d^2\mathbf{v}\\ &= \pi\lambda^2\sum_{k=2}^N (2k-1)(1-k\epsilon)\\ &= \pi\lambda^2\frac{N-1}{6}\left(6N+6-\epsilon\left(4N^2 + 7N + 6\right)\right), \end{align}

so

$$\pi\lambda^2\frac{N-1}{6}\left(6N+6-\epsilon\left(4N^2 + 7N + 6\right)\right)\leq 1$$

$$N+1-\epsilon\left(\frac{4N^2 + 7N + 6}{6}\right)\leq \frac{1}{\pi(N-1)\lambda^2}$$

$$N+1- \frac{1}{\pi(N-1)\lambda^2}\leq \epsilon\left(\frac{4N^2 + 7N + 6}{6}\right)$$

$$\frac{6\left(\pi\left(N^2-1\right)\lambda^2- 1\right)}{\left(4N^2 + 7N + 6\right)\left(\pi(N-1)\lambda^2\right)}\leq \epsilon$$

$$1-\frac{6\left(\pi\left(N^2-1\right)\lambda^2- 1\right)}{\left(4N^2 + 7N + 6\right)\left(\pi(N-1)\lambda^2\right)}\geq 1-\epsilon.$$

Minimizing $N$ gives you about $0.9898$ for $\lambda=1/100$.

On the other hand, I've also been trying to find constructions that give a large value of $c$. I haven't come up with any great ones - the best I have is a circle of radius $\sqrt{\frac{1}{\pi}}$ which gives you a $c$ of about 0.9887. For larger $\lambda$ the best I can think of is something like a "star" with large radius and very many thin "prongs," but I haven't calculated the asymptotics on it yet.

I believe the bound given in step 2 of the solution is sharp iff

$$(\mathcal{P}+\mathbf{u})\cap(\mathcal{P}+\mathbf{v})\subseteq\mathcal{P}\subseteq(\mathcal{P}+\mathbf{u})\cup(\mathcal{P}+\mathbf{v}),$$

but all attempts I've made to find measurable sets for which this is true or nearly true for small vectors have failed. So I'm stuck.

Anyone have any ideas, either on sharper upper bounds on $c$ or a sharper $\mathcal{P}$?

$\endgroup$
  • $\begingroup$ The question at the start is phrased poorly. You should reorder like "Given lambda, what is the smallest possible c>o so that for any P ....". The point is that c depends on lambda and not P. $\endgroup$ – mathworker21 Jul 12 '18 at 0:31
  • $\begingroup$ @mathworker21 You're right; I missed that. I've edited the question accordingly. $\endgroup$ – Carl Schildkraut Jul 12 '18 at 22:08
  • $\begingroup$ Original problem can be solved, the value that half of circumference multiple 1/100 is upperbound. Thinned shape give a small c, maximum case would be about round and small shape, that's circle. $\endgroup$ – Takahiro Waki Jul 17 '18 at 8:26
  • $\begingroup$ @TakahiroWaki Can you formalize that? $\endgroup$ – Carl Schildkraut Jul 17 '18 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.