20
$\begingroup$

This question is inspired by a recent one (and takes a great deal from the answers there). Given a convex subset $\Delta$ of the unit square, let $p(\Delta)$ be the probability that a random line does not intersect $\Delta.$ The exact model for the selection of the lines is that a random point is chosen uniformly on the boundary and then a second is chosen randomly from the union of the other three sides. Consider the circle $\Delta_O$ of radius $\frac1{\sqrt{2\pi}}$ centered at $(\frac12,\frac12),$ I can show that $p(\Delta_0)=0.34470989\dots.$

Let $S$ be the family of convex subsets of the square with area $\frac12.$

What are the best upper and lower bounds you can give on $\sup_{S}p(\Delta)?$

In particular, is there a specific $\Delta \in S$ with $p(\Delta) \gt p(\Delta_O)?$

Here is a certain octagon $\Delta_8$ along with the circle $\Delta_0$ described above. enter image description here

I find that the octagon is the best of its kind but it is not quite as good as the circle. I get that $p(\Delta_8)=0.31984\dots.$ The lower left corner is at about $(0.32606,0.11670).$

Will Sawin in a comment to the question mentioned above observes that an optimal region will have no straight sides and also no corners. Any set $t\Delta_O+(1-t)\Delta_8$ with $0 \lt t \lt 1$ will be in $S.$ I don't know if these are worth investigating very deeply since some other octagon might be better for the purpose. Such a convex combination would still have $8$ corners but the segments would be curved. To deal with the corners on this, or some other $\Delta$ with corners, we could, for a very small positive $\epsilon,$ take all points within $\epsilon$ of a point of $\Delta.$ This would enlarge the area a bit so we would then shrink the smoothed figure to restore the correct area. This smoothing will fix corners but not straight sides (of length exceeding $\epsilon.$)

It seems clear that an optimal region has the same $8$ lines of reflective symmetry as the square. I'm not claiming to have a proof of that, nor am I asking for one.

In an answer to the linked question Will Sawin also makes an impressive start on a proof on finding the optimal set using the Calculus of Variations. I recommend reading it. The question here is more humble, just beat the circle. Perhaps there is a $16$-gon that succeeds or gets close. If so, it could perhaps be massaged to do even better.

An upper bound is $p(\Delta) \lt \frac23.$ It is given by Christian Remling. He calls it crude, and I do think it is pretty far from optimal, but it is also the record that I know of so far and the proof sketched is very nice.

$\endgroup$
  • 6
    $\begingroup$ I've seen some pretty long lines at The Circle in the Square. en.wikipedia.org/wiki/Circle_in_the_Square_Theatre $\endgroup$ – Gerry Myerson Jul 23 '17 at 12:52
  • 6
    $\begingroup$ It is perhaps worth mentioning that if lines are chosen according to a measure that is uniform with respect to orientation and, conditioned on orientation, uniform with respect to translation, then the circle is optimal as a consequence of Crofton's formula: en.wikipedia.org/wiki/Crofton_formula $\endgroup$ – Yoav Kallus Jul 23 '17 at 14:16
  • 3
    $\begingroup$ The area bounded by four hyperbolas, one of which (provided that the left bottom corner of the square is the origin) is $xy=\frac a4$ where $a$ solves the equation $a(1+\log\frac 1a)=\frac 12$ beats the circle slightly. However, I do not think it is optimal either (though it is optimal for a different problem: maximize the probability that a random interval with the endpoints on two adjacent sides of the square misses the region). $\endgroup$ – fedja Jul 23 '17 at 15:46
  • 4
    $\begingroup$ @fedja I don't think the right half is optimal, it can be improved by making it slightly convex. If you just replace it with the pentagon with top vertices $(0,a), (1/2, 1-a), (1,a)$ then we get all lines between $(1,r)$ and $(1,s)$ as long as $r \geq a$, $s \geq a$, $r+s \geq 2-2a$ which is one-half times $(1-a)^2 - (2-4a)^2/2$ which is optimized at $a=3/7$. $\endgroup$ – Will Sawin Jul 23 '17 at 18:56
  • 1
    $\begingroup$ @fedja By a symmetry argument, I believe the differential equation has to have the form $\ddot{y} =f_{\lambda}(x)$ which should be solvable in reasonably explicit form. $\endgroup$ – Will Sawin Jul 24 '17 at 6:17
16
$\begingroup$

Calculus of variation shows that the segment of the boundary of the optimal shape where the tangent line intersects two opposite sides must be a parabola.

To see, this observe that the tangent line is between $(0, y - x \dot{y})$ and $(1, y+ (1-x) \dot{y} )$ so we are trying to maximize the area under the curve $y - x \dot{y}, y+ (1-x) \dot{y} $, which is given by

$$ \int (y - x\dot{y} ) \frac{d}{dx} \left( y+ (1-x) \dot{y} \right) dx $$

$$ = \int (y - x\dot{y} ) (\dot{y} + (1-x) \ddot{y} - \dot{y} ) dx $$

so we can set $$F = (1-x) \ddot{y} (y - x \dot{y} ) - \lambda y$$ and ask to optimize $\int F dx$, which by calculus of variations implies the differential equation $$\frac{dF}{dy} - \frac{d}{d x} \left( \frac{dF}{ d \dot{y}} - \frac{d}{dy} \frac{d^2 F}{d\ddot{y}} \right)= 0$$

We calculate:

$$\frac{d^2 F}{d\ddot{y}} = (1-x) (y - x\dot{y})$$

$$ \frac{d}{dy} \frac{d^2 F}{d\ddot{y}} = - (y - x \dot{y}) + (1-x) ( \dot{y} - \dot{y} - x \ddot{y}) = - (y - x\dot{y} )- x(1-x) \ddot{y} $$

$$ \frac{dF}{ d \dot{y}} =- x (1-x) \ddot{y} $$

$$\frac{dF}{ d \dot{y}} - \frac{d}{dy} \frac{d^2 F}{d\ddot{y}} = y - x\dot{y} $$

$$ \frac{d}{d x} \left( \frac{dF}{ d \dot{y}} - \frac{d}{dy} \frac{d^2 F}{d\ddot{y}} \right) = \dot{y} - x \ddot{y} - \dot{y} = - x \ddot{y} $$

$$\frac{dF}{dy} = (1-x)\ddot{y} - \lambda $$

$$\frac{dF}{dy} - \frac{d}{d x} \left( \frac{dF}{ d \dot{y}} - \frac{d}{dy} \frac{d^2 F}{d\ddot{y}} \right) = \ddot{y} - \lambda $$

and so the solution is a parabola.

In the case of fedja's suggested problem of the maximum area for two opposite lines, we can find the maximum solution with a single boundary segment - it must be given by some equation of the form $y = 1/2 + \alpha (x^2-x +1/6)$ to have area $1/2$, and then the tangent line is between $(0, 1/2 + \alpha ( 1/6 - x^2))$ and $(1, 1/2 + \alpha ( 1/6 - (1-x)^2 ) )$ so the area is given by a $ 1/2 + \alpha/6$ times $1/2 + \alpha/6$ square, minus the corner region given parameterically by $x \to (\alpha x^2, \alpha (1-x)^2)$ which has area $\alpha^2 \int_0^1 (1-x)^2 dx^2 = \alpha^2 \int_0^1 2x (1-x)^2 dx = - \alpha^2/6$ so this is given by optimizing $(1/2 +\alpha/6)^2 - \alpha^2/6$, which is achieved when $2/6 (1/2+\alpha/6) = 2 \alpha/6$, or $\alpha=3/5$, and the probability achieves is $1/2 \left( ( 1/2 + \alpha/6)^2 - \alpha^2/6 \right) = (1/2) (3/5)^2 (5/6) = 3/20$

So the parabolic region $y \geq 1/2 + (3/5) (x^2-x+ 1/6)$ achieves a probability of $3/20$ of a random line through two opposite sides intersecting it, which beats the $1/8$ achieved by the region $y \geq 1/2$ and, I suspect, is optimal for that subproblem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ One possibility would be to just naively combine 4 parabolic and 4 hyperbolic segments to make a reasonable-looking convex body. Solving for area $1/2$ seems annoying, so instead I just looked for a case that gives a smooth curve with a fixed $\lambda$ value. We could take the curve $yx = 1/54$ from $(1/18,1/3)$ to $(1/3,1/18)$, then $y = 1/2 + (x-1/2)^2/2$ from $ (1/3,1/18)$ to $(2/3,1/18)$, and so on around the square. $\endgroup$ – Will Sawin Jul 24 '17 at 8:18
  • $\begingroup$ In fact, I would conjecture that there is actually a unique curve whose segments include four parabolic arcs and four segments of the kind from my previous post, with the same value of $\lambda$, with the transition from one curve to the next tangent and also tangent to the line passing through the appropriate corner, of area $1/2$, and that this is optimal. $\endgroup$ – Will Sawin Jul 24 '17 at 8:55
  • $\begingroup$ I agree. For what it's worth, if my computations are right (30% chance), in the "symmetric angle regime" the intersection points of the tangent line to the body with the axes must move according to the parametric equations $x(t)=c\cosh(\mu t)e^t,y(t)=c\cosh(\mu t)e^{-t}, -T\le t\le T$ for some appropriately chosen $c,\mu,T\ge 0$. From here, you can derive the curve itself, if you need it (I just prefer to parameterize the tangent lines but it is a pure matter of taste). The hyperbola corresponds to the case $\mu=0$. $\endgroup$ – fedja Jul 24 '17 at 12:41
  • $\begingroup$ @fedjaWhat do you mean by symmetric angle regime? The corner? That may be right if you allow different constants for $x$ and $y$, as scaling x and y independently is a symmetry of the differential equation. $\endgroup$ – Will Sawin Jul 24 '17 at 12:46
  • $\begingroup$ Yes, the corner assuming that we have a shape symmetric with respect to the bisector (which is what the current conjecture is). Otherwise the formula is a bit different: $c\cosh(\mu t)$ must be desymmetrized into $ae^{\mu t}+be^{-\mu t}$ and $[-T,T]$ should be $[T_1,T_2]$ but that factor is common for $x$ and $y$. $\endgroup$ – fedja Jul 24 '17 at 12:50
7
$\begingroup$

I guess it won't hurt to post the details of the solutions to the "toy" problems: the separate cases of lines through the adjacent sides and through the opposite sides. Let us consider the adjacent sides case first. It is really cute (IMHO) and I wish that were what was requested. Alas, the life is never easy :-)

I will parameterize the convex domain by the family of its tangent lines. As the point $p$ runs over the boundary of our convex domain (which I may assume to be reasonably smooth and located strictly inside the square without loss of generality) counterclockwise, the endpoints $x$ and $y$ of the corresponding tangent line run counterclockwise along the boundary of the square $x$ being ahead of $y$ (see the picture).

Tangent lines

The corresponding infinitesimal butterflies between "successive" tangent lines sweep the area between our shape and the surrounding square twice. Identifying the points $x,y$ with their distances to the "common corner" (the orange case) or the "common side" (the red case), we see that the butterfly area elements are $$ \frac 12 \frac{(\frac Xx)^2+(\frac Yy)^2}{\frac Xx+\frac Yy}xy\text{ and } \frac 12\frac{X^2+Y^2}{X+Y} $$ respectively where $X=|\dot x|$ and $Y=|\dot y|$ are the speeds of $x$ and $y$. These expressions should integrate to $1$ (twice $\frac 12$). On the other hand, the integral expression for the probability in question involves $$ \frac 18(Xy+Yx)=\frac 18\left(\frac Xx+\frac Yy\right)xy $$ in the corner case and $\frac 18(X+Y)$ in the side case (recall that we do not allow the lines through parallel sides here, so only the right side of the square can be used as the location of the second point for $x$ or $y$ in the red configuration). By Cauchy-Schwarz, the probability element is at most half of the butterfly area element in all cases, whence we can bound the probability by the area between the shape and the surrounding square. In order to have equality, we want the regime with $\frac Xx=\frac Yy$ in the corner case and $X=Y$ in the side case. The first one results in $xy=\operatorname{const}$, i.e., in an arc of hyperbola. The second one corresponds to the rotation around a point. So, we get a shape consisting of 4 hyperbolic arcs. It remains to choose the constant to get the area as requested.

to be continued eventually but not necessarily soon

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Indeed it seems that the circle is not optimal although the improvements I've found only raise the probability slightly and are visually hard to distinguish from a circle. Here is the circle in red and a region $\Delta_h$ bounded by $4$ hyperbolas. Recall that the circle has $p(\Delta_0)=0.34470989\dots.$ It turns out that $p(\Delta_h)=0.34494\dots.$enter image description here

It was suggested that the optimum might be a shape bounded by $4$ hyperbolas near the corners and $4$ parabolas near the middles of the sides. The best I could do with that is $\Delta_{hp}$ shown here with $p(\Delta_{hp})=.34544686\dots.$

enter image description here

The parabola at the bottom is roughly $y=1.221614(x-\frac12)^2+.1045232.$ The transition from the parabola to the hyperbola to its left occurs between $(0.26957, 0.16938)$ and $(0.267287, .170719)$ (the respective endpoints of the polygonal approximations) with the middle of the hyperbola at $(0.213614,0.213614).$

Some disclaimers: I am not certain this is correct. I expected that the contact point of a tangent line rolling around would transition from hyperbola to parabola exactly when its intersection of the line with the square passes a corner and begins to intersect opposite sides. I believe this would maintain a constant area between the tangent and the square.However I don't see that happening here. Also, The later digits may not be exact, I tried to truncate before a small calculated digit. These are actually polygons obtained by sampling (at equally radially spaced points). The area may come out to be less than $\frac12$ in which case the figure is dilated appropriately. This will map parabolas to parabolas but deform hyperbolas. However replacing the deformed sections by a best hyperbola approximation changes the area only slightly. Iterating a few times stabilizes. I did not do this adjusting to $\Delta_h$ so it may be cheated out of a bit.

I don't know if this is really the optimal shape. I could investigate small perturbations of the polygon but have not. I am pretty sure that something similar to a quarter circle in a corner OR a parabola along with most of the top OR the top, with the upper portions of the two sides connected by the arc of a conic could not do as well. I'm not saying it would be hard to rule those out. I just haven't rigorously done so.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, you are right that this one is not optimal, for exactly the reason you state about transition points. I just hoped it would be closer to optimal, as indeed it seems to be. $\endgroup$ – Will Sawin Aug 2 '17 at 10:43

Your Answer

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

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