Find convex closure of certain set

Question

I'm having trouble solving this problem:

Given the set $X\subset\mathbb{R}^2$ defined as $$X=\{(x,y)\in\mathbb{Z}\times\mathbb{R} : y\geq 0,x^2\leq b^2+y\},$$ being $b\in\mathbb{R}$. Is $X$ covex? Study the convex closure of $X$ in $\mathbb{R}^2$ in function of $b$. Define this closure in an analogous way to the set $X$, adding if necessary one new inequality. Note: consider absolute value.

I know how to prove $X$ is not convex, but I don't know how to answer the second question. The first thing I need to do is obviously change the condition $(x,y)\in\mathbb{Z}\times\mathbb{R}$ to $(x,y)\in\mathbb{R}^2$. But after this, I don't know how to express it. I clearly see the shape in my head, but I don't understand how to expess it with just one more inequality. I understand that $$\{(x,y)\in\mathbb{R}^2 : y\geq 0,x^2\leq b^2+y\}$$ is NOT the convex closure of $X$, since you don't need the full parabola $x^2=b^2+y$ as the set's edge (instead, the edge of the convex closure will be an infinte number of segments joining each consecutive intersection points between $x\in\mathbb{Z}$ and $x^2=b^2+y$). I hope I have explained my point correctly

How can I solve this? Any help or hint will be appreciated, thanks in advance

Answer 1

This is just a formal writing following @EDX's advice.

The required set is $$Y = \{(x,y) \in \mathbb{R}^2 \mid y \ge \lfloor x \rfloor^2 - b^2 + \underbrace{(x - \lfloor x \rfloor) (2 \lfloor x \rfloor + 1)}_{=0 \text { if } x \in \mathbb{Z}}\}.$$ It's easy to see that $X \subseteq Y$. The key to prove the convexity of $Y$ is to observe that it's a piecewise linear function. Choose an arbitrary point $x \in \mathbb{R}$ belonging to the interval $[k, k+1)$ with $k \in \mathbb{Z}$, then choose arbitrary $s \in [k,k+1)$. We have to show that $f(s) = \lfloor s \rfloor^2 - b^2 + (s - \lfloor s \rfloor) (2 \lfloor s \rfloor + 1)$ is linear on the closed interval $[k,k+1]$.

We start with some basic observations.

1. The points $P_0 = (k,k^2 - b^2), P_1 = (k+1, k^2 - b^2 + 2k + 1)$ belongs to $X$.
2. The floor function is a step function, and $\lfloor s \rfloor = k$.

Compute the slope of the line segment joining $(k,f(k))$ and $(s,f(s))$, and observe that it's the same as that joining $(k,f(k))$ and $(k+1,f(k+1))$.

$$\frac{f(s)-f(k)}{s - k} = \frac{k^2 - b^2 + (s-k)(2k+1)-(k^2-b^2)}{s - k} = 2k + 1 = f(k+1)-f(k).$$

It's clear that $Y$ is the intersection of upper half-planes whose boundary joins a pair of "adjacent (in the sense of $\mathbb{Z}$ of the $x$-component) points".

$$Y = \bigcap_{k \in \mathbb{Z}} \{(x,y) \in \mathbb{R}^2 \mid y \ge k^2 - b + (2k + 1)x \}$$

As each half-plane above is closed, so does its countable intersection.

I hope you would be convinced that $Y$ is the convex envelop of $X$, even though I've only showed that the boundary points of $Y$ are a convex combination of $X$. (i.e. $\{ (x,y) \in \mathbb{R}^2 \mid y = f(x) \} \in \mathrm{conv}(X)$).

For each $\epsilon > 0$ and $x \notin \mathbb{Z}$ such that $(x,f(x) + \epsilon) \in Y$, write it as a convex combination of $(\lfloor x \rfloor, f(\lfloor x \rfloor) + \epsilon)$ and $(\lfloor x+1 \rfloor, f(\lfloor x+1 \rfloor) + \epsilon)$, which belong to $X$. In other words, if there's an uplift $\epsilon$, just do the same on your chosen pair of adjacent points in $X$.

Answer 2

As we see clearly on the drawing provided by GNUSupporter :

The convex closure of $X$ is the set the one he provided you can see his answer as adding the inequality :

Because the fonction $ f: x \to x^2 -b^2 $ is convex it is under its cords.

You want $y$ to be upper the graph of $f$ but also upper the graph drawn by GNUSupporter :

That condition is the one given by GNU:

$$Y=\{(x,y)\in \mathbb{R}^2 \ y\geq 0, x^2\leq b^2 +y, \ y \geq \lfloor x \rfloor^2-b^2+(x-\lfloor x \rfloor) (2 \lfloor x \rfloor+1) \} $$

but the second one is useless becausse it lies in the third.

Which gives :

$$Y=\{(x,y) \in \mathbb{R}^2 \ y\geq 0, \ y \geq \lfloor x \rfloor^2-b^2+(x-\lfloor x \rfloor) (2 \lfloor x \rfloor+1) \} $$

An advice, if a teacher ask you a question actually quite open saying if necessary. Remember with that kind of question and how it is ask you're rather free to propose a solution as given by GNU the importance is most of the time the methode and the answer more than follwing up too scrupulously. Being more scrupulossly can be a gain of time, energy and also , what is most beautiful, a liberty which allow you to solve an exercise rigourously but with a certain hindsight !