TITLE: A necessary and sufficient condition for optimality of non-smooth convex functions over convex set
QUESTION [2 upvotes]: Let $f:\mathbb{R}^n\rightarrow \mathbb{R}$ be a convex function and $K\subseteq \mathbb{R}^n$ be a convex set. Consider the problem of minimizing $f(x)$ over $x \in K$. It is well known that, if $f$ is differentiable everywhere, then $x^\star$ solves the problem if and only if $\nabla f(x^\star)(y-x^\star)\geq 0,~\forall y \in K$.
Now suppose that $f$ is not differentiable and let $$\partial f(x)=\{g \in \mathbb{R}^n|~~f(y)\geq f(x)+g^T(y-x)~~\forall y \in \mathbb{R}^n\}$$ denote the subdifferential of $f$ at $x$. Are there any necessary and sufficient conditions for optimality that mimic $\nabla f(x^\star)(y-x^\star)\geq 0,~\forall y \in K$, but using subdifferentials for non differentiable functions?

REPLY [1 votes]: One way to think about this is that $x^*$ minimizes $h(x) = f(x) + I_K(x)$ iff $0 \in \partial h(x^*) = \partial f(x^*) + \partial I_K(x^*)$ iff there exists $g\in \partial f(x^*)$ such that $-g$ is in the normal cone to $K$ at $x^*$ iff there exists $g \in \partial f(x^*)$ such that $g^T(y-x^*) \geq 0$ for all $y \in K$.
(Note that this argument uses the subdifferential sum rule, and the fact that the subdifferential of the convex indicator function $I_K$ at $x^*$ is the normal cone to $K$ at $x^*$.)


TITLE: If I ask $2N$ people a yes or no question, what's the probability $N$ say yes?
QUESTION [2 upvotes]: Suppose I ask $2N$ people a yes or no question. The answer are independent binomially distributed random variables. Each individual has his own probability of saying yes. When the $i$th responds, he says yes with probability $p_i$. Moreover,
$$\\p_1,p_2,...,p_{2n} \sim Uniform[0,1]$$
and are independently and identically distributed. What is the probability half of the responders say yes?

I know that
$$\int_0^1p dp$$
Is the probability of voting yes for some individual. I'm inclined to express the probability half of the responders say yes as,
$$\\\int_0^1\binom{2N}{N} p^{N}(1-p)^{N}dp.\\$$
But this seems to impose that $p=p_1,p_2,...,p_{2n}$, which doesn't need to be the case.

REPLY [3 votes]: I am not entirely sure, but here what looks right to me.
Conditioned on $p=(p_1,\dots,p_{2N})$, what you have is a random variable $X_p$ following a Poisson Binomial distribution with parameters $2N$ and $p$. So what you want is the probability that your random variable $X$ equals $N$, which is
$$
\mathbb{P}\{X=N\} = \mathbb{E}\mathbf{1}_{\{X=N\}} = \mathbb{E}[\mathbb{E}[\mathbf{1}_{\{X=N\}}\mid p]]
= \mathbb{E}[\mathbb{P}[X_p = N]]
$$
From the known expression (cf. Wikipedia article) of the pmf of a Poisson Binomial r.v., we have
$$
\mathbb{P}[X_p = N] = \sum_{A\in F_N} \prod_{i\in A} p_i \prod_{j\in A^c} (1-p_j)
$$
so that, by linearity of expectation and independence of the $p_i$'s,
$$\begin{align}
\mathbb{P}\{X=N\} &= \sum_{A\in F_N}\mathbb{E}\left[\prod_{i\in A} p_i \prod_{j\in A^c} (1-p_j)\right]
= \sum_{A\in F_N} \prod_{i\in A} \mathbb{E}[p_i] \prod_{j\in A^c} \mathbb{E}[(1-p_j)]\\
&= \sum_{A\in F_N} \left(\frac{1}{2}\right)^{\lvert A\rvert}\left(\frac{1}{2}\right)^{\lvert A^c\rvert}
= \frac{\lvert F_N\rvert}{2^{2N}}\\
&= \boxed{\frac{1}{2^{2N}}\binom{2N}{N}}
\end{align}$$
(I followed the notation of Wikipedia, writing $F_k$ for the set of all subsets of $k$ integers that can be selected from $\{1,2,3,\dots,2N\}$).


TITLE: Why light moves sideways?
QUESTION [5 upvotes]: Greatings!
I'm trying to understand special relativity and have one question bugging me.
In almost every book or video about the subject there is a thought experiment with moving light clock. I hope I need not elaborate on the sutup and the outcome of the experiment.
So the question is this: When a light source on the MOVING light clock emits a photon of light the path of the photon is triangular.
How this can be?
I thought since light speed is constant in every reference frame the movment of the "emmiter" can't affect the movment of the light so light should shoot right up (from the point of stationary observer) and thus move backward and up from the point of moving observer.
So you see my logic is: light speed is invariant => you can't make it move UP & FORWARD only UP. i.e. you can't change it's direction once it's emited in UP direction. Why the hell light moves sideways then?
And I'm puzzeled. There is flaw in the logic but I don't see it.
Thanks for help.

REPLY [0 votes]: The answer is simple. All motion is frame dependent. Suppose you stand at the junction of one road running north-south and another running east-west.  If I walk along the road to the east, you think you are stationary and I am moving eastwards, but in my frame I am stationary and you are moving west. Someone walking up the north-pointing road will be moving due north in your frame, but in my frame they are walking north-west. Relative to me they have a component of velocity towards the west, but relative to you they do not.
It is almost exactly the same with light. If you fire a laser up the north road, from your perspective it has no component of velocity to the east or west. However, if I walk to the east, I can consider myself to be stationary and so the light in my frame has a component of velocity to the west.


TITLE: Integrate $\int_C \frac{dz}{1+z^2}$ for (a) $\mid z - i\mid = 1$ and (b) $\mid z \mid =2$
QUESTION [3 upvotes]: I want to make sure I remember how to do basic residue calculus problems for an exam, here's a problem:
Integrate $\int_C \frac{dz}{1+z^2}$ if
(a) C is the circumference given by $\mid z - i\mid = 1$
and if
(b) C is the circumference given by $\mid z \mid =2$
Answer:
(a) C is a circle of radius 1 centered at $i$, and $f(z)=\frac{1}{(z-i)(z+i)}$ so it has poles in $\pm i$. Only the positive one is included in the contour. We have $Res(f,i)=\lim_{z\rightarrow i}(z-i)\frac{1}{(z-i)(z+i)}=\frac{1}{2i}$
So $\int_C \frac{dz}{1+z^2}=2\pi i \frac{1}{2i}=\pi$
(b) C is a cirle of radius 2 centered at the origin, it includes both the positive and negative poles of $f(z)$.
To find the residue for the negative pole: $\lim_{z\rightarrow -i}(z+i)\frac{1}{(z+i)(z-i)}=-\frac{1}{2i}$
So $\int_C \frac{dz}{1+z^2}=2\pi i (\frac{1}{2i}-\frac{1}{2i})=0$
Does everything check out? Much appreciated.

REPLY [1 votes]: People seem to be happy with this, I'm posting it as an answer instead of shutting down the post.
(a) C is a circle of radius 1 centered at $i$, and $f(z)=\frac{1}{(z-i)(z+i)}$ so it has poles in $\pm i$. Only the positive one is included in the contour. We have $Res(f,i)=\lim_{z\rightarrow i}(z-i)\frac{1}{(z-i)(z+i)}=\frac{1}{2i}$
So $\int_C \frac{dz}{1+z^2}=2\pi i \frac{1}{2i}=\pi$
(b) C is a cirle of radius 2 centered at the origin, it includes both the positive and negative poles of $f(z)$.
To find the residue for the negative pole: $\lim_{z\rightarrow -i}(z+i)\frac{1}{(z+i)(z-i)}=-\frac{1}{2i}$
So $\int_C \frac{dz}{1+z^2}=2\pi i (\frac{1}{2i}-\frac{1}{2i})=0$


TITLE: Euclidean Algorithm for finding GCD of polynomials
QUESTION [0 upvotes]: Essentially my question is to find the GCD of the following polynomials using the Euclidean algorithm:
$A:= x^5-3x^4+3x^3-2x^2+2x-4$
$B:= x^5-x^4-3x^3-x^2+x+3$
My attempt:
(Each new remainder will be the following letter of the alphabet. )
$A = 1B +(-2x^4+6x^3-x^2-3x-7) \\ B = (-\frac{x}{2}-1)C+(\frac{5}{2}x^3-\frac{7}{2}x^2-11\frac{x}{2}-4) \\C=(-\frac{4}{5}x+\frac{32}{25})D + (-\frac{23}{25}x^2+\frac{21}{25}x-\frac{47}{25}) \\ D=(-\frac{125}{46}x+\frac{700}{529})E \ + (-\frac{6200}{529}x-\frac{800}{529} \\ E= (\frac{12167}{155000}x - \frac{393047}{4805000})F+(-2.0037)$
At this point I assumed the GCD is $1$ as the remainder is constant.. however I'm 99% sure this is wrong due to the actual factorisation of A and B.
$ A = (x-2)(x^2-2x+2)(x^2+x+1) \\ B = (x-1)(x^2-x-3)(x^2+x+1)$
They clearly have a common factor so I'd expect that $GCD(A,B) = (x^2+x+1) $
I'm assuming I'm misunderstanding something fundamental in terms of the Euclidean Algorithm but not entirely sure what.. any help is appreciated!

REPLY [2 votes]: $C = A - B = -2x^4 + 6x^3 - x^2 + x - 7\\
D = B + (\frac 12 x + 1)C = \frac 52 x^3 - \frac 32 x^2 - \frac 32 x - 4$
This appears to be your mistake.
There is no reason why you can't say.
$D = 2B + (x + 2)C =  5 x^3 - 3x^2 - 3x - 8$ to keep it all with integer coefficients.
And sometimes half steps are easier to keep track of.
$E = 5C + 2Dx = 24x^3 - 11x^2 - 11x  - 35\\
F = 24D - 5 E = 17 x^2 +17 x + 17\\
G = x^2 + x  +1$


TITLE: Shortest distance between two points
QUESTION [0 upvotes]: Everyone knows that the shortest distance between two points is a straight line. How can we prove it mathematically?

REPLY [0 votes]: This follows from the Euler-Lagrange equation from the calculus of variations. Let $(a,y(a)),(b,y(b))$ be two points in the plane, where $y$ is a differentiable function on $[a,b]$. The lenght $S$ of this curve  between $a \le x \le b$ is given by:
$$S =\int_{a}^{b}\sqrt{1+\bigg{(}\frac{dy}{dx}\bigg{)}^{2}}dx$$
So we would like to find out which curve $y$ minimizes $S$. Write $F(y') = \sqrt{1+(y')^{2}}$. We have:
$$\frac{\partial}{\partial y} F = 0 \quad \mbox{and} \quad \frac{\partial}{\partial y'}F = \frac{y'}{\sqrt{1+y'}}$$
Thus, using Euler-Lagrange we have:
$$\frac{\partial}{\partial y}F - \frac{d}{dx}\bigg{(}\frac{\partial}{\partial y'}F\bigg{)} = 0 \Rightarrow -\frac{d}{dx}\bigg{[}\frac{y'}{\sqrt{1+(y')^{2}}}\bigg{]} = 0 \hspace{1cm} (1)$$
The solution of equation (1) is given by:
$$ y = \alpha x + \beta$$
which is exactly the equation of a straight line.


TITLE: Is one form of a function more 'true' than another?
QUESTION [2 upvotes]: Here's a function: $f(x) = \frac{x^2}{x}$
Now, if we were to look for the $0$ value, we would end up with a division by zero situation.
By simplifying it to an equivalent function: $f(x) = x$, this is no longer a problem.
Does this mean that the latter function is, in a sense, a more 'true' form of the function? Do both of these forms have the same domain?

REPLY [2 votes]: Good question.
Firstly, let me say that the concept of an "implicit domain" is one of my pet peeves! The day we universally reject such antiquated conventions will be a glorious day for mathematics.
Thus, my answer is that we should never define a function with just with a formula; always define it by specifying a particular domain and codomain.
For example:

Let $f$ denote the unique function $\mathbb{R}\setminus\{0\} \rightarrow \mathbb{R}$ subject to the following condition. $$f(x) = \frac{x^2}{x}.$$

This is a (not-at-all ambiguous, and therefore perfectly acceptable) shorthand for the following, more long-winded formalization.

Let $f$ denote the unique function $\mathbb{R}\setminus\{0\} \rightarrow \mathbb{R}$ such that for all $x \in \mathbb{R}\setminus\{0\}$, we have the following. $$f(x) = \frac{x^2}{x}.$$

Now lets focus our attention on the expression $x$. There's (at least!) two ways of defining a function using this formula. One way defines a function $g : \mathbb{R} \setminus \{0\} \rightarrow \mathbb{R}$, the other a function $h : \mathbb{R} \rightarrow \mathbb{R}$. These are different functions. The first coincides with $f$; that is, $g=f$. The second does not.
That's basically all there is to it.
Actually, there's one more thing that should really be addressed. Both $f$ and $g$ (they're the same function, after all) can be extended in a unique manner to a continuous function $\mathbb{R} \rightarrow \mathbb{R},$ and this function turns out to be $h$.


TITLE: Categories and Homomorphism
QUESTION [1 upvotes]: I understand the notation homomorphism set notation, but I'm a little confused about the necessity of the subnotation. We've used $Hom_C(M,N)$ to represent the homomorphisms from $M$ to $N$ in the category $C$
However, when talking about dual spaces, is this necessary? We write $Hom_k(k,V)$ as the dual space. Isn't the category given? Or am I misunderstanding the subscript $k$?

REPLY [3 votes]: It is quite common throughout mathematics for similar or identical notations to be used with different meanings in different contexts.  In the context of vector spaces over a field (or more generally, modules over a ring), the field (or ring) $k$ is often written as a subscript on "Hom" to indicate that you are considering $k$-linear maps.  In other contexts, you often subscript a Hom-set in a category with the name of the category.  In either context, it is common to drop the subscript entirely when there is little risk of confusion.
(By the way, the dual space is $\operatorname{Hom}(V,k)$, not $\operatorname{Hom}(k,V)$.)

REPLY [2 votes]: Te above guys beat me to it, so I will try to complement the answers. The dual space is $V^*: = Hom_k(V,k)$.
In particular, $V,k$ are also abelian groups, so $Hom(V,k)$ could mean a homomorphism of abelian groups, the subscript clarifies which kind of homomorphisms are you talking about, or over which field (ring).


TITLE: How to find solutions to the gravitational potential metric h
QUESTION [0 upvotes]: I'm working on a problem in which a star of mass M1, radius R1 is surrounded by a thin shell of mass M2, , radius R2. I want to find the solutions to the gravitational potential h in the region in between the star and the shell and region outside both.
Can we assume the mass is stationary, and not too large, and thus use the analogous Poisson's equation (Laplacian of potential = 4*pi*G*rho)?
Or is there some physical reason that we should use the potential equation in the Hilbert gauge (d'Alembertian of tensor potential = 4*pi*G*(energy momentum tensor)/(c^2)?
My thinking is that Poisson's is totally appropriate for this simple situation of a stationary star with a shell mass around it.
Now, I don't see how to use Poisson's equation. I'm getting tripped up with how to consider the two masses. What if, for example, it's a very dense shell which is in fact more massive than the star. That would give a potential radially outward. How do I find a solution to the Laplacian?

REPLY [0 votes]: If the star and the shell are spherically symmetric, you can use the fact that the field of a symmetric distribution at any radius is the same as the field created by a mass point at the center that has the same mass as is closer to the center than the point of interest.  In particular, when you are between the star and the shell you can ignore the shell-it makes no field (though it does change the potential. )


TITLE: Orbit of detached mass
QUESTION [0 upvotes]: I was wondering what precisely would happen to parts detached by objects in orbit. To specify:

Let a large object of mass $m$ is in a stable orbit around a planet with mass $M$ at a distance $r$ from the planet's center. A part of mass $m$ is detached from the mass. splitting the object into two parts $m_1$ and $m_2$, where $m_2<<m_1$. While detaching, mass $m_1$ applies a force $\vec F$ to $m_2$ within an infinitesimally small time. What can be said about the distance to the planet's center $r_2$ of mass $m_2$? Will mass $m_2$ reach a new stable orbit?

I would also like to know how the change in $r_2$ relate to the magnitude and direction of $\vec F$

REPLY [0 votes]: I think you are expecting that the two fragments will fly apart. (If they only become detached so that they are no longer bound together then they will travel together along the original orbit, as in the question What happen to a spoon which is detached from the satellite?
Gravitational bound orbits are generally elliptical. The two fragments will follow separate elliptical orbits with the planet at one focus. The velocities of the fragments (magnitude $v$ and direction angle $\alpha$) can be determined from conservation of momentum and the impulse between them. This is the easy part of the calculation, using familiar collision dynamics.
The new orbits of the fragments can be calculated from their velocities ($v, \alpha$) and radius $r$ at the point of separation. From ($r, v, \alpha)$ you can calculate the orbital parameters eccentricity $e$,  semi-major axis $a$ and its inclination angle $\theta$ with a reference axis. However, the calculation of ($e, a, \theta$) from ($r, v, \alpha$) is not an easy task. For details see answers to Projectile/orbital motion over very long distance which is the same problem except that the launch point is at the surface of the planet.


TITLE: Prove that if $f$ is a real continuous function such that $|f|\le 1$ then $|\int_{|z|=1} f(z)dz| \le 4$
QUESTION [2 upvotes]: I've encountered the following problem in complex analysis:
Prove that if $f$ is a real continuous function such that $|f|\le 1$ then $|\int_{|z|=1} f(z)dz| \le 4$.
I've decomposed $f$ to it's real and imaginary parts and got that it's enough to prove that:
$(\int_0^{2\pi}cos(\theta)g(\theta)d\theta)^2 +(\int_0^{2\pi}sin(\theta)g(\theta)d\theta)^2 \le 16$
Where $g(\theta)=f(e^{i\theta})$.
But now I'm stuck. Any ideas?
Thanks

REPLY [3 votes]: Following the hint by  TheOscillator:

use the fact that there is a complex number $z_{0}=e^{it}$ such that $$z_{0}\int_{|z|=1}{f(z) \, dz}= \left|\int_{|z|=1}{f(z) \, dz}\right|$$

The advantage this gives is that we only have real part to worry about. Writing $z=e^{is}$, the real part of the left hand side becomes
$$
\int_0^{2\pi} -f(e^{is}) \sin(t+s)\,ds $$
Now the triangle inequality reduces this to the integration of $|\sin|$ over an interval of length $2\pi$. This integral is indeed $4$.


TITLE: Determining odds in Blackjack
QUESTION [2 upvotes]: How do you determine the different odds in Blackjack? For example, what would be the difference in odds from using 1, 2, or 3 decks? Also, what would be the difference in odds if you shuffle the deck before each hand instead of after the cards are used up?

REPLY [3 votes]: Generally, as you use more decks you are approaching drawing with replacement instead of without.  The chance of getting a blackjack with one deck is 2(4/52)(16/51), with the 2 being whether you draw the ace first, 4/52 drawing an ace, and 16/51 drawing a 10 count.  If you have a huge number of decks this becomes 2(4/52)(16/52).  If you don't shuffle before the hand, it is impacted by the cards you have seen go by.  If all the aces have already been drawn, the probability is zero.

REPLY [3 votes]: Edward Oakley Thorp went into depth on this subject with his book ${\bf Beat \,\, the \,\, Dealer,}$ which demonstrated mathematically how the house advantage can be overcome in blackjack by card counting.


TITLE: Is infimum achieved?
QUESTION [1 upvotes]: Suppose $V$ is a Banach space, and $V_0$ is a closed subspace of $V$. I know that the following quantity is well-defined for every $w\in V\sim V_0$:
$$\inf\{\|w+v_0\|~|~v_0\in V_0\}$$
Is this infimum ever achieved by a particular $v_0$? If so, why?

REPLY [1 votes]: No. This is true if $V_0$ is a finite-dimensional subspace, or if $V$ is a Hilbert space, but not in general. The following is a counter-example :
Define
$$
V := c_0 := \{(x_n) \in \ell^{\infty} : \lim x_n = 0\}
$$
with the induced (supremum) norm from $\ell^{\infty}$. And let
$$
V_0 = \{ (x_n) \in c_0 : \sum 2^{-n} x_n = 0 \}
$$
I claim that $V_0$ does not have this "best approximation property".

Let $y = (y_n) \in V\setminus V_0$, and set $\lambda := \sum 2^{-n} y_n \neq 0$. Then consider the elements
$$
x^1 := y - \frac{2}{1}\lambda (1,0,0,0, \ldots )
$$
$$
x^2 := y - \frac{4}{3}\lambda (1,1,0,0,0, \ldots )
$$
$$
x^3 = y - \frac{8}{7} \lambda (1,1,1,0,0, \ldots )
$$
and so on, then
$$
\|y - x^n\| = \left ( 1 - 2^{-n}\right )^{-1} |\lambda | \to |\lambda |
$$
Hence, $d(y, V_0) \leq |\lambda |$
However, for any $x = (x_n) \in V_0$, then
$$
|\lambda | = \left | \sum 2^{-n} (y_n - x_n) \right | \leq \sum 2^{-n} | y_n - x_n |
$$
But, since $y\neq x$, and $y_n, x_n \to 0$, there is $n_0 \in \mathbb{N}$ such that
$$
|y_n - x_n | < \|y-x\| \quad\forall n\geq n_0
$$
Hence,
$$
| \lambda | < \sum 2^{-n} \|y-x\| < \|y-x\|
$$
Hence, there is no $x\in V_0$ such that $\|y-x\| = | \lambda |$.

There is also an interesting paper by R.R. Phelps (see this), which connects this best approximation property to a dual "unique hahn-banach extension" property, which might be worth a look.


TITLE: There are no maximal $\mathbb{Z}$-submodules in $\mathbb{Q}$
QUESTION [6 upvotes]: Is it true that $\mathbb{Q}$ viewed as  $\mathbb{Z}$-module (i.e. abelian group) has no maximal $\mathbb{Z}$-submodules? Why ?

REPLY [4 votes]: If you define action of $\mathbb Z$ on $\mathbb Q$ by $q\to nq$ for $q\in \mathbb Q$ and $n \in \mathbb Z $ it is trivial to check that $\mathbb Q$ is an $\mathbb Z$ module.
Now, Let $M$ be maximal submodule of $\mathbb Q$ then $\mathbb Q/M$ is an simple $\mathbb Z$ module. You can also say that it is cyclic module since by simplicity the module generated by elemet should be whole module.
Now, any cyclic $\mathbb Z$ submodule isomorphic to $\mathbb Z/(\langle a \rangle)$ and by simplicity we must have $a$ is prime so;
$$\mathbb Q/M\cong Z_p$$
Thus, we can have homomorphism from $\mathbb Q$ to $Z_p$ with kernel $M$ which is a contradiction.(why? you can simply think the homomorphism between two field $\mathbb Q$ and $Z_p$, it must be the trivial one.)


TITLE: Bayes Theorem on Urnes with Coinflipping
QUESTION [0 upvotes]: I could need your help with this. I got a urn with 2 coins, C1 and C2.
Both have Head and Tails on it.

P(C1=head) = 0.2
P(C1=tails) = 0.8
P(C2=head) = 0.4
P(C2=tails) = 0.6

This is given.
Now I flip 3 times and get in total 2 head and 1 tails. After those results, what is the probability, that I flipped Coin C1?
All i can think of, is the probability to get those relusts, which should be 0.2x0.2x0.8 = 0.032. But that doesn't help me any further. I am supposed to take at most 5 minutes to solve this and i think i am supposed to use Bayes Theorem, if it works here. But i don't have any clue.

REPLY [1 votes]: Bayes in short.

Observe that: $$P(C_1\mid T=2)P(T=2)=P(T=2\mid C_1)P(C_1)\tag1$$
Find $P(T=2)$, $P(T=2\mid C_1)$ and $P(C_1)$ and substitute in $(1)$.
Then the equality enables you to find $P(C_1\mid T=2)$.


TITLE: gram-schmidt (linear algebra)
QUESTION [0 upvotes]: Consider $A = [a_1, a_2, a_3] =
$$
        \begin{bmatrix}
        1 & 1 & 1 \\\
        1 & -1 & 0 \\\
        2 & 0 & 4 \\
        \end{bmatrix}
$
a) From the vectors $a_1, a_2, a_3$ find orthogonal vectors $q_1, q_2, q_3$ by Gram-Schmidt
b) Find the upper triangular matrix $R$ such that $A = QR$ with $Q = [q_1 q_2 q_3]$.
I believe I have found $A_1 =
$$
\begin{bmatrix}
1\\
1\\
2\\
\end{bmatrix}
$, $A_2 =
$$
\begin{bmatrix}
1\\
-1\\
0\\
\end{bmatrix}
$,  and $A_3 =
$$
\begin{bmatrix}
-1\\
-1\\
1\\
\end{bmatrix}
$,  but I'm not sure where to go from there.

REPLY [0 votes]: The vectors you found should be labeled $q_1,q_2,q_3$ instead of $A_1,A_2,A_3$.
You have
\begin{align}
    a_1 &= 1q_1+0q_2+0q_3 \\
    a_2 &= 0q_1+1q_2+0q_3 \\
    a_3 &= \frac{a_3^Tq_1}{q_1^Tq_1}q_1+\frac{a_3^Tq_2}{q_2^Tq_2}q_2+\frac{a_3^Tq_3}{q_3^Tq_3}q_3 \\
    &= \frac{3}{2}q_1+\frac{1}{2}q_2+1q_3
\end{align}
Therefore,
$$
   \begin{bmatrix}a_1 & a_2 & a_3\end{bmatrix} =
   \begin{bmatrix}q_1 & q_1 & q_3\end{bmatrix}\begin{bmatrix}1 & 0 & \frac{3}{2} \\ 0 & 1 & \frac{1}{2} \\ 0 & 0 & 1\end{bmatrix}.
$$


TITLE: Free Groups Are Torsion-Free: proof using cyclically reduced words
QUESTION [0 upvotes]: I am trying to show that

free groups (defined via the universal property) are torsion-free.

I have a hint that says that I should first consider words that are cyclically reduced. That is, if $s_1,...,s_k$ are the generators, then  $w=s_i...s_l$ is cyclically reduced if $s_i\neq s_l^{-1}$.
Now clearly cyclically reduced words are torsion-free but I am unsure how I can go on to use this to show that all words are torsion-free?

REPLY [1 votes]: Hint: Every word is the conjugate of a cyclically reduced word. That is, every word $V$ has the form $V\equiv UWU^{-1}$ where $W$ is cyclically reduced and $U$ is a freely reduced word.
(I am going by the hint you have been given, not by your comment about using the universal property. As far as I am concerned, this does not use the universal property of free groups in any explicit way...)


TITLE: Number of ways to sum up to 12, using only 6 summands (including 0), and order matters
QUESTION [1 upvotes]: This relates to a spatial model, each summand represent a particular location ($IxJ$ grid) where $N$ agents can go. In this case, there are only 6 ($2x3$ grid) possible locations to go and 12 ($N$) agents.
For example,
$$
1 + 1 + 2 + 2 + 2 + 2 \leq 12,
$$
is different than
$$
2 + 2 + 1 + 1 + 1 + 1 \leq 12.
$$
In the first case, just one agent goes to each of the first two locations and two agents go to each of the other locations. Two agents decide not to go to any location. In the second case, two agents go to each of the two first locations, and just one agent go to each of the other locations, and again, two agents decide not go anywhere.
Agents can decide not go anywhere, so that
$$
0 + 0 + 0 + 0 + 0 + 0
$$
or
$$
3 + 2 + 1 + 1 + 1 + 0
$$
are both valid arrangements.
I think this translates well into number theory, in particular combinatorics, but I have not found any way to solve this problem. Composition seems to be restricted to equality and including zero adds more complexity to the problem. I already know the answer to the specific case by checking in matlab using hard-wired code, but I rather have a way to compute the number analytically to generalize the model.
Here is the code, the size of the third dimension of "options" is what I am looking for.
for a1 = 0:N
    for a2 = 0:(N-a1)
        for a3 = 0:(N-a1-a2)
            for a4 = 0:(N-a1-a2-a3)
                for a5 = 0:(N-a1-a2-a3-a4)
                    for a6 = 0:(N-a1-a2-a3-a4-a5)
                        options(:,:,end+1) = [a1, a2; a3 a4; a5, a6];
                    end
                end
            end
        end
    end
end

options = options(:,:,2:end);   % remove first row of zeros

REPLY [1 votes]: Consider doing the following.  Ask the first agent how many she moved.  Write on a piece of paper that many "x" marks.  Then mark an "|" to indicate moving on to the next agent.  Then do the same for the next agent and then the next.  If after the six agents you haven't gotten $12$, mark off the remaining "x" to get $12$ "x" marks.
You will have written on your paper $12$ "x" marks and $6$ "|" marks.
How many ways are there to do that?
You have made $18$ marks and of them $6$ of them are "|"s and the remainder of them are "x"s.  How many ways are there to choose $6$ marks out of $18$ to be "|"s?
There are ${18 \choose 6} = \frac {18!}{6!(18-6)!} = \frac {18!}{6!12!} = \frac {13*14*15*16*17*18}{6!} =  18564$


TITLE: Construction of Sobolev space
QUESTION [1 upvotes]: I am reading about the construction of Sobolev spaces from $L^2$. In the book I read (Introduction to Partial Differential Equations, by Gerald B. Folland) that the operator used to construct those spaces for any $s \in \mathbb{R}$, which is defined to be the operator $\Lambda^s$ such that:
$\widehat{\Lambda^{s}u}(\xi) = (1 + |\xi|^2)^{s/2}\widehat{u}(\xi)$
Where $\widehat{u}$ is the Fourier transform of $u$, is equivalent to the operator $\Lambda^s = (I - (2\pi)^{-2}\Delta)^{s/2}$.
How can you show that? I supposed $\Delta$ is the Laplacian because it is a book about PDE, but I'm not sure either, because I don't get the link between the Laplacian and the Fourier transformation!

REPLY [3 votes]: In general, if $u \in C^2(\mathbb{R}^n) \cap L^2(\mathbb{R}^n)$, we have
$\widehat{\Delta u}(\xi)=\sum_{i=1}^n \widehat{\partial_{xi} \partial_{xi} u}(\xi)=-4\pi^2 |\xi|^2 \widehat{u}(\xi)$
Now, $H^s(\mathbb{R}^n):=\lbrace u \in L^2(\mathbb{R}^n) : \Lambda^s u \in L^2(\mathbb{R}^n) \rbrace$ with $\omega_s(\xi):=(1+|\xi|^2)^{s/2}$, and $\Lambda^s u := \mathcal{F}^{-1}(\omega_s \widehat{u})$, and by Plancherel theorem we have the $H^s$-norm
$\displaystyle \left \| u \right \|_{H^s}= \left \| \Lambda^s u \right \|_{L^2}= \left\| \mathcal{F}(\Lambda^s u) \right\|_{L^2}=\left \| \omega_s \widehat{u} \right \|_{L^2}=\left( \int_{\mathbb{R}^n} |\widehat{u}(\xi)|^2 (1+|\xi|^2)^s d\xi \right)^{1/2}$
Therefore we can write $\Lambda^s = (Id - (1/4\pi) \Delta^{s/2})$.


TITLE: Why do new real numbers show up in Gödel's constructible hierarchy
QUESTION [3 upvotes]: In the "fat" cumulative hierarchy of sets, all the real numbers appear on level $\omega+1$. In Gödel's constructible hierarchy, some real numbers appear at that level, but (if I'm not mistaken) more real numbers show up at later levels. While it is clear to me why not all the reals (of the fat hierarchy) can be defined at level $\omega+1$ of the constructible hierarchy, I need some help understanding exactly why some of them show up later.
Specifically:

Since there are only countable many reals at level $\omega+1$ of the constructible hierarchy, one can diagonalize on them to define a new real. But to do so in the  constructible hierarchy, a bijection between those reals and $\mathbb N$ would have to be definable in there. Is it?
At higher levels one can define the least upper bound of some (non-empty, bounded) set of reals from earlier levels. But this real number might be among the reals already defined. Are there any least upper bounds that are new real numbers?

What exactly are the mechanisms that produce new real numbers at higher levels?

(If there are multiple such mechanisms, I am interested in hearing about several of them. References to relevant literature would also be very much appreciated.)

UPDATE
I'm still looking for some help understanding this. As far as I can tell, the answer below focuses on why there are levels where now real numbers do not show up. I'm trying to understand the opposite. To make it as concrete as possible: why do new real numbers show up at level $\omega+2$?

REPLY [7 votes]: As desired, here is a simple example of a real in the $L_{\omega+2}$ but not in $L_{\omega+1}$:
There is a natural way to interpret $L_\omega$ as $\mathbb{N}$; via this, we can treat elements of $L_\omega$ as Godel numbers for sentences. Then it's not hard to show that, for $\alpha\ge\omega$ and $n\in\omega$, the real coding $Th_n(L_\alpha; \in)$ (the $n$-quantifier fragment of the theory of the structure $(L_\alpha; \in)$ is an element of $L_{\alpha+1}$. And we can "piece together" these fragments if we go up one level: for $\alpha\ge\omega$, the real coding the full theory of $(L_\alpha; \in)$ is an element of $L_{\alpha+2}$.
Moreover, since every element of $L_\omega$ is definable in the structure $(L_\omega; \in)$, it is also not hard to show that every real in $L_{\omega+1}$ is computable from the real coding $Th_n(L_\omega; \in)$ for some $n\in\omega$.
This means:

The real coding the full theory of $(L_\omega;\in)$ is an element of $L_{\omega+2}\setminus L_{\omega+1}$.

Via the Ackermann interpretation noted above, this also tells us:

The real coding the full theory of $(\mathbb{N}; +,\times)$ is in $L_{\omega+2}\setminus L_{\omega+1}$.

Speaking computability-theoretically, yet another way to say this is:

The real $0^{(\omega)}$ is in $L_{\omega+2}\setminus L_{\omega+1}$.

Note that this does not work for every level of $L$ - there is no reason we can't have the real coding $Th(L_\alpha;\in)$ in $L_\alpha$ already, in general (although of course it can't be a definable element of $(L_\alpha; \in)$). But it does show how new reals can show up.
If you like this picture, you may enjoy reading the beginning of Hodes' paper on the mastercode hierarchy.

Here's yet another way we can see new reals appear in $L$; although this one is less direct, it is still pretty cool in my opinion - it uses elementary submodels and absoluteness.
Note that this is very closely related to Asaf's answer; it's really the same thing, phrased differently.
For $\alpha<\omega_1^L$, $L_{\omega_1^L}\models$"$\alpha$ is countable" - that is, there is an injection $f:\alpha\rightarrow\omega$ in $L_{\omega_1^L}$. By "pushing $\alpha$ through this injection," we get in $L_{\omega_1^L}$ a real coding an isomorphic copy of the linear order $(\alpha; \in)$ with domain $\omega$.
Alright, fix $\alpha<\omega_1^L$; I claim there is a real in $L_{\omega_1^L}\setminus L_\alpha$.
Via Lowenheim-Skolem and the Mostowski collapse, let $M$ be a countable transitive model of ZFC with $L_\alpha\subseteq M$. (If you'd rather not assume the existence of a well-founded model of ZFC, just note that we'll only need a finite fragment of ZFC for what follows, and apply the reflection theorem.)
Let $\beta=M\cap Ord$ be the height of $M$, and note that $\alpha<\beta<\omega_1^L$. Note that being an ordinal is a bounded-quantifier property, so absolute: $(i)$ everything $M$ thinks is an ordinal is an ordinal and $(ii)$ everything in $M$ which is an ordinal, $M$ thinks is an ordinal. That is, $Ord^M=M\cap Ord$.
Since $\beta<\omega_1^L$, we must have some real $r\in L_{\omega_1^L}$ coding an isomorphic copy of $(\beta;\in)$ with domain $\omega$; I claim $r\not\in M$, hence $r\not\in L_\alpha$.
To see this, suppose $r\in M$. Coding a well-ordering is a $\Pi^1_1$ fact, so by Mostowski absoluteness $M$ also thinks $r$ codes a well-ordering. Now ZFC proves that every well-ordering is in order-isomorphism with some ordinal; let $\gamma\in M\cap Ord$ be such that $M$ thinks there is an order-isomorphism from the linear order coded by $r$ to $\gamma$. Being an order-isomorphism is a bounded-quantifier property, so absolute between $M$ and $V$; hence we have $\gamma=\beta$. But this is a contradiction: no transitive model can contain its own height.


TITLE: If $n\Delta s_n=o(1)$ is satisfied then $n\log n \Delta s_n=o(1) $
QUESTION [0 upvotes]: Let $(s_n)$ be a sequence of real numbers. I wonder if  $n\Delta s_n=o(1)$  is satisfied then $n\log n \Delta s_n=o(1) $ is also satisfied.
$(\Delta s_n= s_n-s_{n-1})$

REPLY [1 votes]: Consider $s_n=\sum_{k=2}^n\frac 1{k\log k}, n\ge 2.$ Then $\Delta s_n=\frac 1{n\log n},n\ge 3.$ Thus $n\Delta s_n=\frac{1}{\log n}=o(1).$ But then we have that $n\log n\Delta s_n=1\ne o(1).$


TITLE: A bounded sequence has a convergent subsequence
QUESTION [0 upvotes]: Let ${a_n}$ be a bounded sequence of real numbers. Prove that ${a_n}$ has a subsequence that converges to lim sup $a_n$.
Thanks!

REPLY [2 votes]: Hint: What is the definition of $\limsup$? Try to use the definition and a sequence involving something like $1/n$ to construct such a subsequence.

REPLY [1 votes]: $\limsup a_n$ is, by definition, the largest limit point of the sequence $a_n$. When you work with Real numbers (or, more generally, when you work with 1st-countable spaces), for every limit point, $a$ , there is a sequence of points that converge to $a$.


TITLE: If you roll a die 5 times, what is the probability that you roll at least one five?
QUESTION [1 upvotes]: If you roll a die 5 times, what is the probability that you roll at least one five.

Is it p(1/5), or do I need to do a bionomcdf, I'm confused.

REPLY [3 votes]: HINT:
Probability of no five in $5$ rolling is $$\left(\frac56\right)^5$$
Probability of at least one five $=1-$ Probability of no five


text:
\begin{document}

\maketitle

\begin{abstract}
For coprime integers $N,a,b,c$, with $0<a<b<c<N$, we define the set
$$ \{ (na \! \! \! \! \pmod{N}, nb \! \! \! \! \pmod{N}, nc \! \! \! \! \pmod{N}) : 0 \leq n < N\}. $$
We study which parameters $N,a,b,c$ generate point sets with long shortest distances between the points of the set in dependence of $N$ and relate such sets to lattices of a particular form.
As a main result, we present an infinite family of such lattices with the property that the normalised norm of the shortest vector of each lattice converges to the square root of the Hermite constant $\gamma_3$. We obtain a similar result for the generalisation of our construction to $4$ and $5$ dimensions.
\end{abstract}

\section{Introduction}

We are interested in point sets
$$ \mlattice:=\{ (na \! \! \! \! \pmod{N}, nb \! \! \! \! \pmod{N}, nc \! \! \! \! \pmod{N}) : 0 \leq n < N\}, $$
in which $\mathbf{v} =(a,b,c)$ such that $0<a<b<c<N$ and $\gcd(N,a)=1$, which ensures that we have $N$ different points in the cube $[0,N-1]^3$.
Defining the shortest distance between points in $\mlattice$ as
$$ \lambda^{\ast}(\mlattice):= \min_{\substack{\mathbf{x} \neq\mathbf{y}, \\ \mathbf{x},\mathbf{y} \in \mlattice}} \| \mathbf{x} - \mathbf{y} \|, $$
we ask:
\begin{enumerate}
\item[(Q1)] How long can the shortest distance between points of such sets be in dependence of $N$?
\item[(Q2)] How to explicitly construct sets with long shortest distances?
\end{enumerate}
We start with simple bounds on $\lambda=\lambda^{\ast}(\mlattice)$. By the definition of our sets, the shortest possible distance between two points is $\sqrt{6}$ for a difference vector containing $1,-1,\pm 2$. On the other hand, assume that $\lambda$ is a shortest distance. Our point sets always contain $(0,0,0)$ and are always contained in the cube $[0,N-1]^3$. Therefore, a ball of radius $\lambda$ centered at $(0,0,0)$ (resp. its intersection with the cube $[0,N-1]^3$ which is $1/8$ of the ball) will never contain any other point of the set. In particular, we can attach such a fraction of a ball of radius $\lambda$ to any point in the set. This yields a simple upper bound on $\lambda$ since we know that our point set is contained in a cube of volume $(N-1)^3$ and we can attach a fraction of an empty ball of radius $\lambda$ to every point. Therefore,
\begin{equation} \label{heuristic1}
\sqrt{6} \leq \lambda^{\ast}(\mlattice) \leq C \cdot N^{2/3},
\end{equation}
for a constant $C >0$.

The main aim of this note is to answer (Q1) and (Q2).
We provide an upper bound for the maximal, normalised shortest distance between two points in sets of the form $\mlattice$ and we relate these sets to particular lattices.
Furthermore, in Theorem \ref{thm2} we present a parametrised family of such lattices whose normalised shortest distance converges (from below) to $C$ as the parameter goes to infinity.

In the following we recall some basic notions and relate our point sets to lattices in $\RR^3$ before we state our main results and discuss previous work in Section \ref{sec:main}. Section \ref{sec:lattice} contains a detailed discussion of numerical results as well as of a remarkable lattice while Section \ref{sec:proofs} contains the proofs our main results.
Finally, in Section \ref{sec:multiD} we discuss the extension of our construction to dimensions $4$ and $5$.

\subsection{Lattices and reduced bases}
We introduce the main concepts surrounding lattices and refer to \cite{CS} for more information.
Let $\mathbf{V}=\{\mathbf{v}_1, \ldots, \mathbf{v}_d\}$ be linearly independent vectors in $\RR^d$. The lattice generated by $\mathbf{V}$ is the set
$$ \Lambda(\mathbf{V}) = \left\{ \sum_{i=1}^{d} x_i\cdot \mathbf{v}_i: x_i \in \ZZ \right\} = \{ \mathbf{V} \cdot \mathbf{x}: \mathbf{x} \in \ZZ^d \} $$
of all integer linear combinations of the vectors in $\mathbf{V}$, and the set $\mathbf{V}$ is called a basis for the lattice. Two bases $\mathbf{V}, \mathbf{V}'$ generate the same lattice, i.e. $\Lambda(\mathbf{V})=\Lambda(\mathbf{V'})$, if and only if there exists an integer unimodular matrix $\mathbf{U}$ such that $\mathbf{V}=\mathbf{V}' \mathbf{U}$.
This is also the reason why it makes sense to define the \emph{(co)volume} of a lattice, i.e.
$$ \covol(\Lambda(\mathbf{V})) = | \det M_\mathbf{V} |, $$
in which $M_\mathbf{V}$ is the square matrix whose rows are the basis vectors $\mathbf{v}_i$, $1\leq i \leq d$ of an arbitrary lattice basis $\mathbf{V}$.
For $\Lambda=\Lambda(\mathbf{V})$ and $1 \leq i \leq d$ the \emph{$i$-th successive minimum} $\lambda_i(\Lambda)$ is the radius of the smallest closed ball centred at the origin and containing at least $i$ linearly independent lattice vectors. In particular, $\lambda_1(\Lambda)$ is the length of the shortest vector of $\Lambda$.
Finally, the \emph{Hermite constant} $\gamma_d$ is (can be) defined as
$$  \sqrt{\gamma_d}= \sup_{\Lambda} \frac{\lambda_1(\Lambda)}{\covol(\Lambda)^{1/d}},$$
in which the supremum is over all $d$-dimensional lattices $\Lambda$.
Thus, the Hermite constant is an upper bound on the maximal length of short lattice vectors in Euclidean space and is known only for $1\leq d \leq 8$ as well as $d=24$; in particular
$$\gamma_2=2/\sqrt{3}, \ \ \gamma_3=2^{1/3}, \ \ \gamma_4=2^{1/2} \ \ \text{ and } \ \ \gamma_5=2^{3/5}.$$
Now we restrict to three dimensional lattices.
\begin{definition} \label{reduced}
A basis $\mathbf{V}=\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3 \}$ of a three dimensional lattice in $\RR^3$ is \emph{(Minkowski-) reduced} if its vectors satisfy:
\begin{enumerate}
\item[(B.1)] $\|\mathbf{v}_1 \| \leq \|\mathbf{v}_2 \| \leq  \|\mathbf{v}_3 \|$;
\item[(B.2)] $\|\mathbf{v}_2 + x_1 \mathbf{v}_1 \| \geq \| \mathbf{v}_2\| $ and $\| \mathbf{v}_3 + x_2 \mathbf{v}_2 + x_1 \mathbf{v}_1 \| \geq \| \mathbf{v}_3\| $ for all integers $x_1, x_2$.
\end{enumerate}
\end{definition}
We refer to \cite{semaev} for a three-dimensional lattice reduction algorithm and to \cite{stehle} for a characterisation of Minkowski-reduced lattice bases in arbitrary dimension $d$. Importantly, the shortest vector in a reduced basis is always the shortest vector of the lattice.
In fact, a basis of a $d$-dimensional lattice that reaches the $d$ minima must be Minkowski-reduced, but a Minkowski-reduced basis may not reach all the minima, except the first four (see \cite{waerden}).

\subsection{The underlying lattice of $\mlattice$}
A first important observation is that our point sets can be obtained as intersections of the cube $[0,N-1]^3$ with three-dimensional integer lattices and the shortest distance in our point sets is given by the shortest vector of the underlying lattices. (Note however that the shortest vector of the underlying lattice need not be an element of our sets!)
A second observation is that the shortest distance of a point set does not change when we change the order of the generating vector; i.e. $\lambda^{\ast}(\mlattice)=\lambda^{\ast}(\mmlattice)$ if $\mathbf{v}=(a,b,c)$ and $\mathbf{v}'=(a,c,b)$ or any other permutation of $a,b,c$. Hence, we can assume $a<b<c$.
In particular, our assumptions on $N,a,b,c$ allow us to restrict to generating vectors of the form $(1,b,c)$, since we can always solve the congruence
\begin{equation} \label{restriction} a \cdot n' \equiv 1 \pmod{N}. \end{equation}
Therefore, we can replace the generating vector $(a,b,c)$ with $(n'a,n'b,n'c)=(1,b',c')$ in which $n'$ is such that $n'a \equiv 1 \pmod{N}$, $n'b \equiv b' \pmod{N}$ and $n'c \equiv c' \pmod{N}$ generate the same set of points. Restricting to generating vectors of the form $(1,b,c)$ gives a particularly simple generating matrix for the underlying lattices.

\begin{lemma} \label{lem:basis}
Let $\mathbf{v}=(1,b,c)$ with $1 < b<c < N$. Then
\begin{equation} \label{modLattice} \mlattice = \begin{pmatrix} 0 & 0 & 1 \\ 0 & N & b \\ N & 0 & c \end{pmatrix} \ZZ^3 \cap [0,N-1]^3 \end{equation}
\end{lemma}

\begin{proof}
Note that we can always find unique integers $x,y$ such that $ 0<Nx+nb < N $ and $ 0<Ny+nc < N $ for $1\leq n \leq N-1$. Every non-trivial point in $\mlattice$ can thus be obtained by multiplying the matrix with $(y,x,n)$. On the other hand it is easy to see that these are the only vectors in $\ZZ^3\setminus\{\mathbf{0}\}$ that yield points in $[0,N-1]^3$. Finally, multiplying with $(0,0,0)$ gives $(0,0,0)$.
\end{proof}

For a given point set $\mlattice$, write $\Lambda(\mlattice)$ for the underlying lattice.
Lemma \ref{lem:basis} can be used to conclude that the shortest distance in our point sets is given by the shortest vector of the underlying lattices.

\begin{lemma}\label{lem:short}
In the above notation, we have that $ \lambda^{\ast}(\mlattice) = \lambda_1(\Lambda(\mlattice)). $
\end{lemma}
\begin{proof}
By Lemma \ref{lem:basis} every point in $\mlattice$ can be written as an \emph{integer} linear combination of the vectors of a \emph{reduced} basis $\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ of the underlying lattice. We identify a point  $\sum_{i=1}^3 x_i \mathbf{v}_i$ in $\mlattice$ with its coordinates $(x_1,x_2,x_3)$ with respect to the reduced basis. If we fix the first coordinate, i.e. set $x_1=k$ for $k \in \ZZ$, we see that all such points $(k,x_2,x_3)$ lie on the hyperplane spanned by $\mathbf{v}_2$ and $\mathbf{v}_3$ and translated by the constant vector $k \cdot \mathbf{v}_1$.

We assume for contradiction that for every point $(x_1,x_2,x_3)$ in $\mlattice$ the corresponding pair of points $(x_1 \pm 1, x_2, x_3)$ lies outside of $[0,N-1]^3$. In other words, that there is no pair of points of $\mlattice$ whose difference is $\mathbf{v}_1$.
Since the cube $[0,N-1]^3$ (interpreted as a compact, solid set) has no holes, this assumption implies that for fixed $(x_1,x_2,x_3)$ also points $(x_1 \pm k, x_2, x_3)$ for $k \in \ZZ \setminus \{ -1,0,1\}$ lie outside of the cube. Now take an arbitrary point $(x_1,x_2,x_3)$ in $\mlattice$. Due to its lattice structure $\mlattice$ contains all integer points of the intersection of $[0,N-1]^3$ with the hyperplane spanned by $\mathbf{v}_2$ and $\mathbf{v}_3$ and translated by $x_1 \cdot \mathbf{v}_1$. However, for all such points and, again because the cube has no holes, $\mlattice$ does not contain any point on parallel hyperplanes of the form $(x_1 \pm k, x_2, x_3)$ for arbitrary but fixed $k \in \ZZ \setminus \{ 0\}$.
This implies that all points of $\mlattice$ lie on a hyperplane spanned by the two longer vectors of the reduced basis and potentially translated by a constant multiple of $\mathbf{v}_1$. Since $\mlattice$ always contains $(0,0,0)$ we see that we actually have $x_1=0$.

A simple area argument (similar to the one in the introduction) shows that if all $N$ points of $\mlattice$ lie on the intersection of the cube with a single hyperplane, then $\|\mathbf{v}_2\|$ is $\mathcal{O}(\sqrt{N})$. However, this contradicts the assumption that $(x_1 \pm 1, x_2, x_3)$ lie outside of the cube for every $(x_1,x_2,x_3)$ in $\mlattice$.

To see this, we first note that a ball of radius $ \|\mathbf{v}_2\|/2$ centered at the centroid of the intersection of the hyperplane with the cube has to contain at least one point $(x_1,x_2,x_3)$ of $\mlattice$ lying on the hyperplane. Next we center at this point a second ball of radius $\|\mathbf{v}_2\|$ which has to contain the points $(x_1 \pm 1, x_2, x_3)$, one on each side of the plane, because $\mathbf{v}_2$ is at least as long as $\mathbf{v}_1$. This second ball is contained in a third ball centred again at the centroid of the plane and of radius $3\|\mathbf{v}_2\|/2$. We call the two halves of the ball on opposite sides of the plane \emph{hemispheres}.
Assuming that the centroid of the plane is at the center of the cube shows that the distance to all faces of the cube is at least $(N-1)/2$ and hence the third ball is fully contained in the cube (for $N$ large enough) which contradicts our assumption.
In case that the centroid is not at the center of the cube, it can be shown by a (a)symmetry argument that at least one of the hemispheres has to be fully contained in the cube, giving the same conclusion.
\end{proof}

\section{Main results}
\label{sec:main}
\subsection{Maximal shortest distance in three-dimensions}
We use the connection to lattices and their shortest vectors to refine the upper bound on the longest shortest distance.
We start with an intuitive argument. It is well known and was first shown by Gauss in 1831 that the face-centered cubic (FCC) lattice
\begin{equation} \label{fcc}  \Omega:= \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0& 1 &1 \end{pmatrix} \ZZ^3 \end{equation}
gives the densest (sphere) lattice packing in $\RR^3$. In fact, the FCC lattice gives the densest packing among all lattices according to the famous \emph{Kepler Conjecture} which was finally settled by Hales and Ferguson \cite{hales, lagarias} utilising an approach of Fejes T\'{o}th \cite{FT} as well as state-of-the-art formal proof techniques \cite{hales2}; see also \cite{szpiro}. Importantly, the shortest vector in the FCC lattice is exactly twice the radius of the spheres which are centered at the nodes of the lattice. We can refine the volume argument of the previous section to get an accurate value for the constant in the upper bound.

We recall that the the FCC lattice can be built out of the basic cube in Figure \ref{fig:basicCube}.
Ignoring boundary effects, each of the $N$ points is contained in $8$ basic cubes and each basic cube contains $4$ lattice points. Thus, we can build $2N$ basic cubes with edge length $\ell$.
We are looking for the maximal edge length $\ell$ such that all $2N$ basic cubes fit into $[0,N-1]^3$:
$$ \max_{\ell \in \RR} \ 2N \ell^3 \leq (N-1)^3 \ \ \ \ \Rightarrow \ \ \ \ \ell \approx \frac{N^{2/3}}{\sqrt[3]{2}} . $$
The shortest distances between the nodes of this lattice are the face diagonals. Thus, we get an accurate idea of the constant $C$ in \eqref{heuristic1}:
$$ C \approx \frac{1}{\sqrt[3]{2}} \sqrt{2} = 2^{1/6} \approx 1.122.$$

This argument can be made exact using the notion of the \emph{Hermite constant} of a lattice as well as Lemma \ref{lem:basis} and \ref{lem:short}. From Lemma \ref{lem:basis} we deduce that the covolume of our particular lattices is $N^2$. Hence,
$$ \frac{(\lambda^{\ast}(\mlattice))^2}{(N^2)^{2/3}} \leq \gamma_3 = 2^{1/3}  \ \ \Rightarrow \ \  \lambda^{\ast}(\mlattice) \leq 2^{1/6} N^{2/3}.$$

\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[scale=0.35]

\node at (0,0) {$\bullet$};
\node at (5,5) {$\bullet$};
\node at (7,2) {$\bullet$};
\node at (2,7) {$\bullet$};

\draw[thick] (0,0) -- (5,0) -- (5,5)--(0,5) --(0,0);
\draw[thick] (5,0) -- (7,2) -- (7,7) -- (5,5);
\draw[thick] (0,5) -- (2,7)--(7,7);
\draw[thick,dashed] (0,0) -- (2,2)--(7,2);
\draw[thick,dashed] (2,7)--(2,2);

\draw[ultra thick,->] (0,0)--(2,7);
\draw[ultra thick,->] (0,0)--(7,2);
\draw[ultra thick,->] (0,0)--(5,5);

\node at (2.5,-0.7) {$\ell$};
\node at (-0.7,2.5) {$\ell$};
\node at (0.5,6.5) {$\ell$};

\end{tikzpicture}
\end{center}
\caption{Basic building block of FCC lattice.} \label{fig:basicCube}
\end{figure}

\subsection{The two-dimensional case}
In \cite{paus2} the two-dimensional variant of the problem was studied. It is well known that the hexagonal lattice
\begin{equation} \label{hexLattice} \Lambda_h = \begin{pmatrix} 1 & 1/2 \\ 0 & \frac{\sqrt{3}}{2} \end{pmatrix} \ZZ^2
\end{equation}
maximises the packing density in $\RR^2$; see \cite{fuk11,rogers58,rogers}. We define
$$\mlatticee:=\{ (na \! \! \! \! \pmod{N}, nb \! \! \! \! \pmod{N}) : 0 \leq n < N\}$$
and $\lambda^{\ast}(\mlatticee)$ as in the three dimensional case.
It turns out that the shortest distance in any two-dimensional set $\mlatticee$ satisfies
$$\sqrt{2} \leq \lambda^{\ast}(\mlatticee) \leq \sqrt{N} \cdot \sqrt{\gamma_2}.$$
Set $n=4s+3$ and define
$$ \frac{b_s}{N_s}=[0,b_1,b_2, \ldots, b_n]=[0,2,1,2,1,\ldots, 1,2] $$
via this particular continued fraction expansion.
Note that this continued fraction converges to $(\sqrt{3}-1)/2$.
It was then shown that the particular family of integer lattices
$$ X_s=  \begin{pmatrix} 0 & 1 \\ N_s & b_s \end{pmatrix} \ZZ^2$$
converges to (a rotated and scaled version of) the hexagonal lattice as the parameter $s$ approaches infinity and the normalised length, $\lambda^{\ast}(\Pi_{N_s,(1,b_s)})/\sqrt{N}$, of the shortest distance converges to $\sqrt{\gamma_2}$.

\subsection{Main result and numerical observations}
Having the upper bound and knowing that the problem can be fully resolved in two dimensions motivates to look for optimal lattices in three dimensions.
As a main result we show how to construct lattices, $\Lambda(\mlattice)$, whose normalised shortest distance is arbitrarily close to $2^{1/6}$.

\begin{theorem} \label{thm:main}
For every $\varepsilon >0$ there exist infinitely many pairs $(N,\mathbf{v})$ such that
$$\frac{\lambda^{\ast}(\mlattice)}{N^{2/3}} > 2^{1/6} - \varepsilon .$$
\end{theorem}
See Theorem \ref{thm2} in Section \ref{sec:proofs} for an explicit construction of such lattices and Theorem \ref{thm3} in Section \ref{sec:multiD} for a natural generalisation to $d=4$ and $d=5$. Our construction is based on extensive numerical analysis of all lattices, $\Lambda(\mlattice)$, up to $N=310$; see Figure \ref{fig:allN} (left). From these observations it appears at first as if it is not possible to obtain lattices with the longest possible shortest distances. The best lattice we can find up to $N=310$ is for the parameters $N=244$ with $\mathbf{v}=(1,13,169)$. We will study this remarkable lattice which led to our explicit construction in the next section.

\begin{figure}
\includegraphics[scale=0.5]{allN.pdf} \ \ \ \ \
\includegraphics[scale=0.5]{allN2.pdf}
\caption{\emph{Left:} The normalised length of the longest shortest vector in base $N$ among all lattices with generating vectors of the form $(1,b,c)$ with $1< b<c <N$. The green line at $2^{1/6}\approx 1.122$ illustrates the upper bound, while the second green line is at 1 and illustrates what can be achieved with cubic lattices. \emph{Right: } The red dots show improvements when allowing all generating vectors $(a,b,c)$ with $\gcd(N,a,b,c)=1$.} \label{fig:allN}
\end{figure}

Furthermore, we present a similar construction in Theorem \ref{thm1} of lattices such that the normalised shortest distance converges to 1. While the first family of lattices can be interpreted as an approximation of the FCC lattice, the second family approximates a cubic lattice.
To see this, set $N=n^3$ and look at the set
\begin{equation*} G_n= \begin{pmatrix} n^2 & 0 & 0 \\ 0 & n^2 & 0 \\ 0 & 0 & n^2 \end{pmatrix} \ZZ^3 \cap [0,N-1]^3.
\end{equation*}
Then
$$\frac{\lambda^{\ast}(G_n)}{N^{2/3}} = \frac{n^2}{n^2} = 1.$$
We close this section with an open problem for which we expect an affirmative answer.
\begin{problem}
Prove (or disprove) that there exists an absolute $\varepsilon >0$ such that for every $N>N_0$ there is a generating vector $\mathbf{v}=(1,b,c)$ with $1<b<c <N$ and
$$ \frac{\lambda^{\ast}(\mlattice)}{N^{2/3}} > 1+\varepsilon. $$
\end{problem}

\begin{remark}
If we relax the condition on the generating vector to $\gcd(N,a,b,c)=1$, then we can also get very good lattices for small $N$ as the examples $N=20$, $\mathbf{v}=(6,15,18)$ for which we get $\lambda^{\ast}(\mlattice)/N^{2/3} = 1.0942\ldots$ or $N=78$, $\mathbf{v}=(15,65,75)$ with $\lambda^{\ast}(\mlattice)/N^{2/3} = 1.09965\ldots$ show.
However, in general it seems that there is no systematic improvement as shown in Figure \ref{fig:allN} (right) at least not for $10\leq N \leq 80$.
\end{remark}

\section{A remarkable lattice}
\label{sec:lattice}

The lattice for $N=244$ and $\mathbf{v}=(1,13,169)$ has several remarkable properties which helped to find the family of lattices presented in Theorems \ref{thm1}-\ref{thm3} and which gives an idea why lattices with long shortest vectors seem so rare and hard to find.
First, we notice that $b^2=c$, i.e. $13^2=169$, and that $b\cdot c = b^3 = 2197 \equiv 1 \pmod{244}$. This property has important implications. If we look at the three two-dimensional orthogonal projections of the lattice, i.e. the lattices generated by
$$
\begin{pmatrix}  0 & 1 \\ 244 & 13 \end{pmatrix},
\begin{pmatrix}  0 & 1 \\ 244 &169 \end{pmatrix},
\begin{pmatrix} 0 & 13 \\ 244 & 169  \end{pmatrix},
$$
we see that they are all copies of the same two-dimensional lattice modulo $244$; see Figure \ref{fig:projections}.

\begin{figure}
\includegraphics[scale=0.35]{pic13.pdf} \quad \quad
\includegraphics[scale=0.35]{pic169.pdf} \quad \quad
\includegraphics[scale=0.35]{pic13169.pdf}
\caption{The three projections of the lattice $\Pi_{244,\mathbf{v}}$ with $\mathbf{v}=(1,13,169)$. The first $13$ points of each lattice are in red.} \label{fig:projections}
\end{figure}

The second lattice can be obtained from the first via a rotation by $\pi/2$ and a reflection on the $x$-axis:
$$ (1,b) \cdot  \begin{pmatrix}  0 & -1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix}  1 & 0 \\ 0 & -1 \end{pmatrix} = (b,1) = (b\cdot 1, b \cdot c).$$
Thus, there is a bijection between the two lattices; the point $(n,bn)$ in the first lattice is obtained as point $(k,kc)$ for $k=bn$ in the second lattice.
Similarly, we see that there is also a bijection between the first and third lattice using both conditions on the parameters; i.e. $bc \equiv 1 \pmod {244}$ and $b^2 \equiv c \pmod {244}$. We have that
$$(1,b) \equiv (b^2 \cdot b, b^2 \cdot c) \pmod{244},$$
and hence the point $(n,bn)$ in the first lattice is obtained as point $(kb,kc)$ in the third lattice for $k=b^2 n$.
An easy calculation shows that the first of the three two-dimensional lattices has a reduced basis of the form $(1,13), (19,3)$; this corresponds to the points with indices $n=1$ and $n=19$.
Using the bijections of the indices of the points that we have just established, we can translate these two vectors and see that we obtain these vectors for indices $k=b=13$ and $k=19b=3$ in the second lattice as well as $k'=b^2=c=169$ and $k'=19b^2=-39$ in the third lattice. Interestingly, the three three-dimensional vectors for $n=1$, $k=b$, $k'=c$ give three variations of the vector $(1,b,c)$ thanks to our assumptions, whereas the vectors for $n=19$, $k=3$ and $k'=-39$ are
\begin{equation} \mathbf{v}_1=\begin{pmatrix} 19 \\ 3 \\ 39 \end{pmatrix},
\mathbf{v}_2=\begin{pmatrix} 3 \\ 39 \\ 19 \end{pmatrix},
\mathbf{v}_3=\begin{pmatrix} -39 \\ -19 \\ -3 \end{pmatrix}
\end{equation}
and as such a reduced basis of the lattice.
Hence, we obtain
\begin{equation}\label{equ1} \frac{\lambda(\Pi_{244,(1,13,169)})}{244^{2/3}} = \frac{\sqrt{1891}}{244^{2/3}} = 1.11366\ldots \end{equation}
This lattice is a rhombohedral lattice which is an almost perfect approximation of the FCC lattice.
The angle $\alpha$ between the edges of the rhomboid is given as
$$ \alpha = \arccos \left( \frac{\mathbf{v}_1 \cdot \mathbf{v}_2}{\| \mathbf{v}_1\| \|\mathbf{v}_2 \|} \right)
= \arccos \left( \frac{\mathbf{v}_1 \cdot \mathbf{v}_3}{\| \mathbf{v}_1\| \|\mathbf{v}_3 \|} \right)
=\arccos \left( \frac{\mathbf{v}_2 \cdot \mathbf{v}_3}{\| \mathbf{v}_2\| \|\mathbf{v}_3 \|} \right) = 1.06572 \ldots$$
which is almost the angle $\pi/3 = 1.0472\ldots$ obtained for the FCC lattice via

$$\arccos \left( \frac{(1,1,0) \cdot (1,0,1)}{\| (1,1,0)\| \|(1,0,1) \|} \right) = \pi/3 .$$

\subsection{A general procedure?}
The calculations in the previous section suggest the following general procedure:
Assume $N,b,c$ are such that $bc\equiv 1 \pmod{N}$ and $b^2 \equiv c \pmod{N}$ (or $bc\equiv -1 \pmod{N}$ and $b \equiv c^2 \pmod{N}$).
Then it is easy to see, using the same index bijections as before, that the three two-dimensional projections of the lattice are indeed always variants of the same lattice.
And it is tempting to hope that the resulting lattice is again rhombohedral such that

the vectors of the reduced basis are permutations of $$(\pm (x \pmod N), \pm (xb \pmod N), \pm (xb^2 \pmod N))$$ where
representatives of each class are taken from the interval $[-(N-1)/2, (N-1)/2]$ as in the example
for $N=244$ and $x$ being the non-trivial index of the shortest vector in the two-dimensional lattice. The length of the shortest vector should then be given as $\|(x,x b,x b^2)\|$.
It turns out, that the shortest vector is in general indeed of this form. Unfortunately, it also seems that in general only two of the three vectors of the reduced basis are of this form, while the third vector is (very) different. Thus, in general we do not obtain a rhombohedral lattice approximating the FCC lattice. Even worse, systematic experiments show that the third basis vector has a much larger norm in general, generating a lattice that is far from being rhombohedral.

As an example we look at $N=366$ and $\mathbf{v}=(1,13,169)$. We have that $b\cdot c = b^3 = 2197 \equiv 1 \pmod{366}$ and $b^2=c$. The three two-dimensional projections are variants of the lattice spanned by $(0,366)$ and $(1,13)$ with reduced basis $(1,13)$ and $(-28,2)$. Hence, in the above notation $x=-28$, $xb=-28 \cdot 13 \equiv 2 \pmod{366}$ and $xb^2 = -28 \cdot 169 \equiv 26 \pmod{366}$.
However, we observe that
\begin{equation} x+ xb + xb^2 = x(1 + b + b^2) \equiv 0 \pmod{366}\end{equation}
-- a property which makes it impossible to get a reduced basis as in the case of $N=244$. This seems to be the generic case for examples of this kind. Indeed, the reduced basis of the three dimensional lattice $\Pi_{366, \mathbf{v}}$ is
\begin{equation} \mathbf{v}_1=\begin{pmatrix} -28 \\ 2 \\ 26 \end{pmatrix},
\mathbf{v}_2=\begin{pmatrix} -2 \\ -26 \\ 28 \end{pmatrix},
\mathbf{v}_3=\begin{pmatrix} 61 \\ 61 \\ 61 \end{pmatrix}.
\end{equation}
Hence,
$$ \frac{\lambda(\Pi_{366, \mathbf{v}})}{366^{2/3}} = \frac{2\sqrt{366}}{366^{2/3}} = 0.7477\ldots, $$
and similarly for other lattices of this form and generated by $(1,13,169)$; see Table \ref{table1}.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$N$ & $x$ & $bx$ & $bx^2$ &  $\lambda^{\ast}(\Pi_{N,\mathbf{v}})/N^{2/3}$\\
\hline
61 & -4 & 9 & -5& 0.7127\\
122 & 10& 8 & -18& 0.7830\\
183 & -14& 1& 13 & 0.5935\\
\hline
244 & 19 &3&39& 1.11366 \\
366 &-28&2&26& 0.7477\\
549 & -42 &3&39& 0.8560\\
\hline
732 &-56&4&52& 0.9421 \\
1098 &-84&6&78& 1.0785\\
$2196$ &-168&12&156& $1.0032^\ast$\\
\hline
\end{tabular}
\end{center}
\caption{Lattices satisfying the conditions $bc\equiv 1 \pmod{N}$ and $b^2 \equiv c \pmod{N}$ for $\mathbf{v}=(1,13,169)$. $^\ast$The shortest vector for $N=2196$ is given by $(1,13,169)$; see Theorem \ref{thm1}.}
\label{table1}
\end{table}

\section{Two infinite sets of lattices}
\label{sec:proofs}
The results in Table \ref{table1} and for similar sets of examples suggest that while the case of $N=244$ seems highly exceptional and mysterious there may be two general patterns for bases of the form $N=b^3-1$ and $N=(b^3-1)/2$ for integers $b>0$. We explore these examples in the following and note that Theorem \ref{thm2} implies Theorem \ref{thm:main}.
\begin{theorem} \label{thm1}
For an integer $m>2$ let $N=m^3-1$ and $\mathbf{v}=(1,m,m^2)$. Then
$$\lambda^{\ast}(\Pi_{N,\mathbf{v}}) = \sqrt{1+m^2+m^4}$$
such that
$$ \lim_{m\rightarrow \infty} \frac{\lambda^{\ast}(\Pi_{N,\mathbf{v}})}{N^{2/3}} = 1. $$
\end{theorem}

\begin{proof}
We prove the theorem by showing that
\begin{equation} \mathbf{v}_1=\begin{pmatrix} 1 \\ m \\ m^2 \end{pmatrix},
\mathbf{v}_2=\begin{pmatrix} -m \\ -m^2 \\ -1 \end{pmatrix},
\mathbf{v}_3=\begin{pmatrix} -m^2 \\ -1 \\ -m \end{pmatrix} \end{equation}
is a reduced lattice basis for the lattice
\begin{equation*} \begin{pmatrix} 0 & 0 & 1 \\ 0 & m^3-1 & m \\ m^3-1 & 0 & m^2 \end{pmatrix}. \end{equation*}
First, we recall that two lattices with bases $\mathbf{B}$ and $\mathbf{B'}$ are equivalent if there exists a unimodular matrix $\mathbf{U}$ such that $\mathbf{B}\cdot \mathbf{U}=\mathbf{B'}$. We observe that
\begin{equation}
\begin{pmatrix} 1 &-m &-m^2\\ m&-m^2 &-1\\ m^2& -1 &-m\end{pmatrix}
\begin{pmatrix} m & 0&1\\ 1&-m &0\\ 0& 1 &0\end{pmatrix}
=\begin{pmatrix} 0 & 0 & 1 \\ 0 & m^3-1 & m \\ m^3-1 & 0 & m^2 \end{pmatrix}
\end{equation}
And the determinant of the second matrix is indeed 1.
Next, we show that $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3$ form a reduced basis.
The first condition in Definition \ref{reduced} is obviously satisfied since all three vectors have the same set of entries. The second condition
$$ \left \| \begin{pmatrix} -m \\ -m^2 \\ -1 \end{pmatrix} + x_1 \begin{pmatrix} 1 \\ m \\ m^2 \end{pmatrix} \right \| =
\left \| \begin{pmatrix} x_1 - m \\ x_1 m- m^2 \\ x_1 m^2 - 1 \end{pmatrix} \right \|
\geq \left \| \begin{pmatrix} -m \\ -m^2 \\ -1 \end{pmatrix} \right \|$$
follows from the observation that
$$
1+m^2+m^4 + x_1^2 (m^4+m^2+1) -2x_1(m^3 + m^2 + m) \geq 1 + m^2 + m^4,
$$
for all $x_1\in \ZZ$ and $m>2$.
This is obviously true for all $x_1 \geq 2$ and all $x_1 \leq 0$. For $x_1=1$, we need that
\begin{equation} \label{cond1}
m^4+m^2+1 - 2m^3 - 2m^2 - 2m \geq 0,
\end{equation}
which holds for all integers $m>2$.
In a similar way, we can also verify that $\| \mathbf{v}_3 + x_2 \mathbf{v}_2 + x_1 \mathbf{v}_1\| \geq \|\mathbf{v}_3\|$.
In this case the inequality reduces to
\begin{align*}
(m^4+m^2+1)(1 + x_1^2 +x_2^2) + (m^3+m^2 +m)(2x_1 - 2x_2 - 2x_1 x_2) \geq m^4+m^2+1.
\end{align*}
Since $(x_1-x_2)^2 + 2(x_1 - x_2) \geq 0$ unless $x_1-x_2=-1$, it is easy to see that the inequality holds for $m\geq 1$ and $x_1, x_2$ with $x_1+1\neq x_2$. Now, assume $x_1+1=x_2$; in this case,
$$ -1 = x_1^2 +(x_1+1)^2  -2x_1^2 - 2x_1 - 2.$$
and the inequality can be reduced to the above \eqref{cond1}.
Hence, the basis is indeed reduced and the length of the shortest vector in the lattice is $\sqrt{1+m^2 + m^4}$.
\end{proof}

\begin{theorem} \label{thm2}
Let $b=2k+1$ be odd and set $N=\frac{b^3-1}{2}$, $\mathbf{v}=(1,b,b^2)$. Then we have
$$ \lim_{k\rightarrow \infty} \frac{\lambda^{\ast}(\Pi_{N,{\mathbf{v}}})}{N^{2/3}} =  2^{1/6} $$
\end{theorem}

\begin{proof}
We prove the theorem by showing that
\begin{equation} \mathbf{v}_1=\begin{pmatrix} -k \\ -k(2k+1) \\ k+k(2k+1) \end{pmatrix},
\mathbf{v}_2=\begin{pmatrix} -k(2k+1) \\ k+k(2k+1) \\ -k \end{pmatrix},
\mathbf{v}_3=\begin{pmatrix}  k+k(2k+1) +1\\ k+1  \\ k+k(2k+1) +k +1 \end{pmatrix} \end{equation}
is a reduced lattice basis for the lattice
\begin{equation*} \begin{pmatrix} 0 & 0 & 1 \\  0&\frac{(2k+1)^3-1}{2} & (2k+1) \\  \frac{(2k+1)^3-1}{2} & 0&(2k+1)^2 \end{pmatrix}. \end{equation*}
First, we observe that
\begin{equation}

(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3) \cdot
\begin{pmatrix}  1+k& -k& 1\\ k &1+k &1\\ k&k &1 \end{pmatrix}
= \begin{pmatrix} 0 & 0 & 1 \\  0 &\frac{b^3-1}{2} & b \\ \frac{b^3-1}{2}&0  & b^2 \end{pmatrix}
\end{equation}
And the determinant of the second matrix is indeed 1.
Next we have to check that $\| \mathbf{v}_2 + x_1 \mathbf{v}_1\| \geq \| \mathbf{v}_2\|$.
We have that $\| \mathbf{v}_2\|^2 = 2k^2 (3 + 6k + 4k^2)$ and the above inequality reduces to
$$ 2k^2 (3 + 6k + 4k^2) (1-x_1+x_1^2) \geq 2k^2 (3 + 6k + 4k^2), $$
which is true for $k\geq 1$ and all integers $x_1$.
Finally, we have to show that
$$\|  \mathbf{v}_3 + x_2  \mathbf{v}_2 + x_1 \mathbf{v}_1 \| \geq \| \mathbf{v}_3 \|$$
for all integers $x_1, x_2$.
We have that $\|\mathbf{v}_3 \|^2 =(1+2k+2k^2)(3 + 6k + 4k^2)$.
Setting $\alpha=3 + 6k + 4k^2$, the inequality can be simplified to
$$ (1+2k +2k^2) \alpha + 2k^2 \alpha (x_1^2 + x_2^2 + x_1 - x_2 - x_1 x_2) \geq (1+2k+2k^2) \alpha,$$
and hence to
$$x_1^2 + x_2^2 + x_1 - x_2 - x_1 x_2 \geq 0,$$
Depending on the signs of $x_1$ and $x_2$

we either rewrite this expression as $x_1^2 + x_2^2 + x_1- x_2(1+x_1)$ in case $x_1$ and $x_2$ have the same sign
or as $x_1^2 + x_2^2 + x_1(1-x_2) -x_2$ in case $x_1$ and $x_2$ have opposite signs to see that this inequality holds in each case and for all pairs of integers $x_1, x_2$.
Thus, we get that
$$\lim_{k\rightarrow \infty} \frac{\lambda^{\ast}(\Pi_{N,{\mathbf{v}}})}{N^{2/3}} = \lim_{k \rightarrow \infty} \frac{\sqrt{2}\sqrt{k^2(3 + 6k + 4k^2)}}{(k (3 + 6 k + 4 k^2))^{2/3}} = 2^{1/6}.$$
\end{proof}

\begin{figure}
\includegraphics[scale=0.5]{optimal.pdf}
\caption{Illustration of the convergence of the normalised length of the shortest vector of $\Pi_{N,\mathbf{v}}$ to $2^{1/6}$. Here, $2N=(2k+1)^3-1$ and the $x$-axis represents $k$; i.e. for $k=50$ we have $N=515150$ and $\mathbf{v}=(1,101,10201)$.
The red dashed line is at $1.1136$; i.e. at the value obtained for $N=244$ with $(1,13,169)$.} \label{fig:convergence}.
\end{figure}

\begin{remark}
We can calculate the value of $k$ needed to get a lattice whose normalised shortest vector is longer than for the exceptional lattice $\Pi=\Pi_{244,(1,13,169)}$. In \eqref{equ1} we calculated that $\lambda^{\ast}(\Pi)/244^{2/3}=\sqrt{1891}/244^{2/3}\approx 1.1136$, which is only improved for $k>31$ or $N\geq 137312$; see Figure \ref{fig:convergence}.
\end{remark}

\section{Higher dimensions}
\label{sec:multiD}

It is possible to generalise our construction to higher dimensions.
We define $\mlatticeI$ and $\mlatticeII$ analogously to the two- and three-dimensional cases for parameter vectors
$$ \mathbf{v} = (a_1, \ldots, a_d),$$
with $d=4$ or $d=5$, $0<a_1< \ldots < a_d <N$ and $\gcd(N,a_1)=1$. Furthermore, we define
$ \lambda^{\ast}(\mlatticeI)$ and $ \lambda^{\ast}(\mlatticeII)$ as in the three dimensional case.

Using a similar volume argument as in the introduction for the three dimensional case, we get that
$$ \lambda^{\ast}(\mlatticeI) \leq C_4 \cdot N^{3/4} \ \ \ \text{ and } \ \ \ \lambda^{\ast}(\mlatticeII) \leq C_5 \cdot N^{4/5}. $$
Lemma \ref{lem:basis} generalises as well and, therefore, we see that $\covol(\Lambda(\mlatticeI))=N^3$ and $\covol(\Lambda(\mlatticeII))=N^4$. Thus, we get from the definition of the Hermite constant that
\begin{align*}
\lambda^{\ast}(\mlatticeI) &\leq \covol(\Lambda(\mlatticeI))^{1/4} \cdot \sqrt{\gamma_4}  = N^{3/4} \cdot 2^{1/4}, \\
\lambda^{\ast}(\mlatticeII) &\leq \covol(\Lambda(\mlatticeII))^{1/5} \cdot \sqrt{\gamma_5}  = N^{4/5} \cdot 2^{3/10}. \\
\end{align*}

We can mimic Theorem \ref{thm2} to obtain the following result for $d=4$ and $d=5$.
\begin{theorem} \label{thm3}
Let $b=2k+1$ be odd and set $N=\frac{b^4-1}{2}$, $\mathbf{v}=(1,b,b^2,b^3)$. Then we have
$$ \lim_{k\rightarrow \infty} \frac{\lambda^{\ast}(\mlatticeI)}{N^{3/4}} =  2^{1/4}. $$
Similarly, let $b=2k+1$ be odd and set $N=\frac{b^5-1}{2}$, $\mathbf{v}=(1,b,b^2,b^3,b^4)$. Then we have
$$ \lim_{k\rightarrow \infty} \frac{\lambda^{\ast}(\mlatticeII)}{N^{4/5}} =  2^{3/10}. $$
\end{theorem}

\begin{proof}[Sketch of the proof]
We start with $d=4$. Analogously to the proof of Theorem \ref{thm2} we can show that
\begin{equation} \mathbf{v}_1=\begin{pmatrix} -k \\ -kb \\ -kb^2 \\k+kb+kb^2 \end{pmatrix},
\mathbf{v}_2=\begin{pmatrix} -kb \\ -kb^2 \\ k+kb+kb^2 \\ -k \end{pmatrix},
\mathbf{v}_3=\begin{pmatrix} -k-kb-kb^2 \\ k \\ kb \\ kb^2 \end{pmatrix},
\mathbf{v}_4=\begin{pmatrix}  k+kb+1\\ 2k+kb+kb^2+1  \\ k+kb+1\\ 2k+kb+kb^2+1\end{pmatrix} \end{equation}
is a Minkowski-reduced lattice basis (see \cite[Section 2.2]{stehle} for a definition of reduced basis in more than 3 dimensions and \cite[Theorem 2.2]{stehle} for a list of conditions to check) for the lattice
\begin{equation*} \begin{pmatrix} 0 & 0 & 0 & 1 \\  0& 0& \frac{(2k+1)^4-1}{2} & (2k+1) \\ 0& \frac{(2k+1)^4-1}{2} &0 & (2k+1)^2 \\   \frac{ (2k+1)^4-1}{2} & 0& 0 &(2k+1)^3 \end{pmatrix}. \end{equation*}
From this we get that
$$\lim_{k\rightarrow \infty} \frac{\lambda^{\ast}(\mlatticeI)}{N^{3/4}} =
\frac{k \sqrt{\left(4 k^2+6 k+3\right) (2 k (k+1)+1)}}{\sqrt{2} (k (k+1) (2 k (k+1)+1))^{3/4}} = 2^{1/4}.$$

Finally, we can construct $5$-dimensional lattices in a similar fashion; i.e. let $b=2k+1$ be odd and set $N=\frac{b^5-1}{2}$, $\mathbf{v}=(1,b,b^2,b^3,b^4)$.
It can be shown that
{\small \begin{equation*} \mathbf{v}_1=\begin{pmatrix} -k \\ -k b \\ -k b^2 \\ -k b^3 \\ 4k(k + 1)(2k^2 + 2k + 1) \end{pmatrix},
\mathbf{v}_2=\begin{pmatrix} k b^2\\ k b^3\\ -4k(k + 1)(2k^2 + 2k + 1)\\ k\\ k b \end{pmatrix},
\mathbf{v}_3=\begin{pmatrix} -k b^3 \\ 4k(k + 1)(2k^2 + 2k + 1)\\ -k \\ -k b\\ -k b^2 \end{pmatrix},
\end{equation*}
\begin{equation*}
\mathbf{v}_4=\begin{pmatrix}  -4k(k + 1)(2k^2 + 2k + 1)\\ k\\ k b\\ k b^2\\ k b^3 \end{pmatrix},
\mathbf{v}_5=\begin{pmatrix}  (2k^2 + 2k + 1)b\\ (2k^2 + 2k + 1) b^2\\ (4k^2 + 2k + 1)(k + 1)\\ (4k^2 + 2k + 1)(k + 1)b\\ 2k^2 + 2k + 1\end{pmatrix}
\end{equation*} }
is a Minkowski-reduced lattice basis for the lattice
\begin{equation*} \begin{pmatrix} 0&0 & 0 & 0 & 1 \\  0& 0& 0& \frac{(2k+1)^5-1}{2} & (2k+1) \\ 0&0& \frac{(2k+1)^5-1}{2} &0 & (2k+1)^2
\\ 0& \frac{(2k+1)^5-1}{2} &0 &0& (2k+1)^3
\\   \frac{ (2k+1)^5-1}{2} & 0& 0 &0 &(2k+1)^4 \end{pmatrix}. \end{equation*}
Having a Minkowski-reduced basis ensures, by a result of van der Waerden \cite{waerden}, that the four shortest vectors in the basis achieve the first four successive minima of the lattice.
Thus, we see that the shortest vector is of the form
$$ (-k, \ -k b,\ -k b^2,\ -k b^3,\ k + k b + k b^2 + k b^3), $$
such that
$$\lim_{k\rightarrow \infty} \frac{\lambda^{\ast}(\mlatticeII)}{N^{4/5}} = 2^{3/10}.$$
\end{proof}

\section*{Acknowledgments}
I would like to thank one anonymous reviewer who brought \cite{stehle} to my attention, who inspired the results of Section \ref{sec:multiD} and whose very constructive and detailed feedback greatly improved an earlier version of this manuscript.

config: arxiv


TITLE: Getting the equation of an ellipse using the constant and the foci
QUESTION [5 upvotes]: Find the equation of the ellipse with the foci at (0,3) and (0, -3) for which the constant referred to in the definition is $6\sqrt{3}$
So I'm quite confused with this one, I know the answer is $3x^2+2y^2=54$ through trial and errror, but is there any way to solve it without trial and error?
The constant referred to is the sum of the distances from the foci right? How do I use it? I've been experimenting with how you can get $6 \sqrt3$ from the equation like using distance formula etc. I'm kinda stuck with this one, can someone please explain thanks!

REPLY [3 votes]: The sum of the distances to the foci is $6\sqrt{3}$.  Via the "distance formula," this translates to
$$\sqrt{x^2+(y-3)^2}+\sqrt{x^2+(y+3)^2}=6\sqrt{3}.$$
Now let us grind. Rewrite as
$$\sqrt{x^2+(y-3)^2}=6\sqrt{3}-\sqrt{x^2+(y+3)^2}.$$
Square both sides. We arrive at
$$x^2+(y-3)^2=108 -12\sqrt{3}\sqrt{x^2+(y+3)^2} +x^2+(y+3)^2.$$
There is some cancellation. After the cancellation, we can divide through by $12$ and arrive at
$$\sqrt{3}\sqrt{x^2+(y+3)^2}=9+y.$$
Square both sides again. Again, there is some cancellation, and we arrive at
$$3x^2+2y^2=54.$$

REPLY [1 votes]: Let $(x,y)$ be a point of ellipse then from definition
$$\sqrt{(x-0)^2+(y-3)^2}+\sqrt{(x-0)^2+(y+3)^2}=6\sqrt{3}$$
$$\sqrt{x^2+(y-3)^2}+\sqrt{x^2+(y+3)^2}=6\sqrt{3}$$
$$2x^2+2y^2+18+2\sqrt{(x^2+(y+3)^2)(x^2+(y-3)^2)}=108$$
$$x^2+y^2+9+\sqrt{(x^2+(y+3)^2)(x^2+(y-3)^2)}=54$$
$$(x^2+y^2-45)^2=(x^2+(y+3)^2)(x^2+(y-3)^2)$$
$$(x^2+y^2)^2-90x^2-90y^2+45^2=x^4+x^2(y+3)^2+x^2(y-3)^2+(y^2-9)^2$$
$$2x^2y^2+y^4-90x^2-90y^2+45^2=x^2(2y^2+18)+y^4-18y^2+81$$
$$-90x^2-90y^2+45^2=18x^2-18y^2+81$$
$$108y^2+72x^2=36\cdot54$$
$$3x^2+2y^2=54$$

REPLY [1 votes]: Note that the general form of the equation for an ellipse is $$\left(\frac{x}{a}\right)^2+\left(\frac{y}{b}\right)^2=1.$$You are right that the constant they give is the sum of the distances from the foci, and note that it is $2a$ (why?). This means we have the equation $$\left(\frac{x}{3\sqrt{3}}\right)^2+\left(\frac{y}{b}\right)^2=1.$$ We can use the Pythagorean theorem to solve for $b$ since we know what the center of the ellipse is and we know the sum of the distances. Hence, solving for $b$ gives $$b=2\sqrt{(3-0)^2+(y-0)^2}=6\sqrt{3}=\sqrt{18}=3\sqrt{2}.$$Plugging these values in, we have $$\frac{x^2}{27}+\frac{y^2}{18}=1\Longrightarrow 2x^2+3y^2=54.$$


TITLE: Lipschitz condition and boundedness imply unique solution
QUESTION [1 upvotes]: Let $(X,\vert\vert\cdot\vert\vert)$ be a Banach space and $f:\mathbb R \times X \to X$ continuous and linearly bounded in its second variable, i.e. there are functions $\alpha, \beta \in C(\mathbb R; \mathbb R_0^+) \cap L^1(\mathbb R)$ such that $$\vert\vert f(t,v)\vert\vert \leq \alpha(t)+\beta(t)\vert\vert v\vert\vert$$ for any $(t,v) \in \mathbb R \times X$.
Thus, every solution of $$u'(t)=f(t,u(t)), u(t_o)=u_o \in X$$$t,t_0\in \mathbb R$ is bounded.
If $f$ now satisfies a Lipschitz condition on $X$, how can I show that the initial value problem is uniquely solvable?

REPLY [3 votes]: The Picard iteration is
$$
P(y)(t)=y_0+\int_0^tf(s,y(s))\,ds.
$$
The difference of two iterated functions is bounded by
$$
\|P(y)(t)-P(u)(t)\|\le \int_0^t L·\|y(s)-u(s)\|\,ds
$$
The difference of the twice iterated functions is
\begin{align}
\|P^2(y)(t)-P^2(u)(t)\|
&\le \int_0^t L·\|P(y)(r)-P(u)(r)\|\,dr
\\
&\le L^2\int_0^t \int_0^r \|y(s)-u(s)\|\,ds\,dr
\qquad(0\le s\le r\le t)
\\
&= L^2\int_0^t \int_s^t\, dr·\|y(r)-u(r)\|\,dr
\\
&= L^2\int_0^t (t-s)·\|y(s)-u(s)\|\,ds
\end{align}
Continuing this one finds
\begin{align}
\|P^n(y)(t)-P^n(u)(t)\|&\le L^n \int_0^t \frac{(t-s)^{n-1}}{(n-1)!}·\|y(s)-u(s)\|\,ds\\[1em]
\implies \qquad
\|P^n(y)-P^n(u)\|_∞&\le  \frac{L^n ·T^n}{n!}·\|y-u\|_∞
\end{align}
in $C([-T,T],X)$.
For the function sequence $P^n(y_0)$ this leads to
\begin{align}
\|P^n(y_0)-P^m(y_0)\|_∞&\le \frac{L^m ·T^m}{m!}·\|P^{n-m}(y_0)-y_0\|_∞\\
\text{and}\qquad
\|P^k(y_0)-y_0\|_∞&\le \sum_{j=0}^{k-1}\|P^{j+1}(y_0)-P^{j}(y_0)\|_∞
\\
&\le\|\sum_{j=0}^{k-1}\frac{L^j ·T^j}{j!}\|P(y_0)-y_0\|_∞<e^{LT}\|P(y_0)-y_0\|_∞
\end{align}
From which one concludes that the function sequence is Cauchy, thus converges, and that to a fixed point of the Picard iteration, and thus to a solution of the initial value problem.
Uniqueness follows because $(LT)^n<n!$ for some large enough $n$ so that for two fixed points $u,y$
$$
\|y-u\|=\|P^n(y)-P^n(u)\|\le \frac{(LT)^n}{n!}\|y-u\|<\|y-u\|
$$
which can only be true for $u=y$.
Since there are no restrictions on $T$, any solution can be extended to all of $\Bbb R$.


TITLE: Is there any significant meaning of the gradient of a matrix?
QUESTION [1 upvotes]: Is there any significant meaning of the gradient of a matrix? What does it imply?
For example in Matlab:
F = [ 2 4 5; 5 6 9; 0 1 3];
[Fx, Fy] = gradient(F);

Fx =

2.0000    1.5000    1.0000
1.0000    2.0000    3.0000
1.0000    1.5000    2.0000

Fy =

3.0000    2.0000    4.0000
-1.0000   -1.5000   -1.0000
-5.0000   -5.0000   -6.0000

How about the quiver(Fx, Fy) as shown below attached image?

REPLY [3 votes]: The definition provided by Matlab is clear enough: the command computes numerical derivatives (i.e., finite differences) in the horizontal and vertical directions. This is what you use if $F$ represents the values of some function sampled along a rectangular grid, and you want an approximation to the derivatives of $F$. The plot shows the directions in which the function grows the fastest (steepest ascent).
In the specific example of $F$ being greyscale intensity, the derivatives will measure how much the  intensity changes between adjacent points. Large values of derivative may indicate an edge in the image; thus, truncating $|Fx|+|Fy|$ at some large value may serve as a primitive edge-detection algorithm. Of course, the real edge-detection algorithms are more sophisticated and look at more than just the difference of adjacent values.
By the way, I want to emphasize the difference between matrix-in-mathematics and matrix-in-matlab. Matrix-in-mathematics is something that represents a linear transformation. Matrix-in-matlab is any rectangular array filled with numbers, e.g., the result of evaluation of a function along a grid. The latter does not naturally represent any linear transformation; we are unlikely to ask what the rank, range and kernel are for this thing. Gradient makes sense for some matrices-in-matlab, but not for those that are matrices-in-mathematics.


TITLE: What will be the effect on a rigid body if two unlike unequal parallel forces act on the body?
QUESTION [0 upvotes]: What will be the effect on a rigid body if two unlike unequal parallel forces act on the body? Will the body translate or rotate or both? If they rotate, with respect too which point will they rotate?

REPLY [1 votes]: The same laws of motion apply here too. Get the net force to see how the center of mass moves and the net torque about the center of mass to see how the body rotates.
So unless the net torque is zero about the center of mass, the body is going to translate and rotate at the same time.
Consider the general case of two unequal opposite forces $F_1$ and $F_2$ each at a distance $d_1$ and $d_2$ from the center of mass at opposite sides. The force act along the y axis and we track the vertical acceleration of the center of mass $\ddot{y}$, as well as the rotational acceleration $\ddot{\theta}$. Finally we find the center of rotation along the x-axis relative to the center of mass as $ r= - \frac{\ddot{y}}{\ddot{\theta}} $.

Linear Motion

$$ (F_1)  + (-F_2) = m \ddot{y} \;\Rightarrow\;  \ddot{y} = \frac{F_1-F_2}{m} $$

Rotational Motion

$$ (d_1) (F_1) + (-d_2) (-F_2) = I_C \ddot{\theta} \; \Rightarrow \; \ddot{\theta} = \frac{d_1 F_1 + d_2 F_2}{I_C} $$
Where $m$ is the mass and $I_C = m \kappa^2$ is the mass moment of inertia about the center of mass, and $\kappa$ the radius of gyration.

Center of Rotation

$$ r = - \frac{\ddot{y}}{\ddot{\theta}} = -\frac{ (F_1-F_2) I_C }{ (d_1 F_1 + d_2 F_2) m} = -\frac{(F_1-F_2) \kappa^2}{d_1 F_1 + d_2 F_2} $$
Now lets consider the fringe cases:

Rotation about the center of mass, $r=0$. This happens only when the two forces are equal in magnitude $F_1 = F_2$.
Pure translation, $r = \infty$. This happens only when the net torque about the center of mass is zero $d_1 F_1 + d_2 F_2 =0$.

In any other case you have simultaneous translation and rotation about the center of rotation.

There is a shortcut to finding the center of rotation. Consider $d$ the distance where the combined forces act through. Essentially $\sum M = d \sum F$, or $$ d = \frac{d_1 F_1+d_2 F_2}{F_1-F_2} $$
Now consider the mass moment of inertia $I_C$, and the radius of gyration $\kappa$. They are related by $I_C = m \kappa^2$.
The center of rotation is found by
$$ r = -\frac{I_C}{m d} = -\frac{\kappa^2}{d} $$
The negative sign here means that $r$ is located on the opposite side of $d$. This means that the center of rotation is purely a geometric quantity as only relates to distances and the radius of gyration. All of these quantities are a function of the shape of the body only.
Stated backwards, if the center of mass is a distance $r$ from the pivot point (center of rotation) then the axis of percussion (axis where momentum needs to be applied to stop the motion) is at a distance $ d = \frac{\kappa^2}{r} $ from the center of mass in the opposite side.
That is why a baseball bat (approx. cylinder of length $\ell$ with center of mass at $r=\frac{\ell}{2}$) has its axis of percussion (sweet spot) at a distance $d$ from the handle of
$$ d = r + \frac{I_C}{m\,r} = \frac{\ell}{2} + \frac{\ell}{6} = \frac{2 \ell}{3} $$


TITLE: How do I find the equation for estimated ratios, 1700:13, 1275:7, 450:3?
QUESTION [2 upvotes]: In the game SCP: Secret Laboratory, there's an enemy character called SCP-049 who can kill players and then resurrect them after a set number of seconds. These are the times that I've plotted out so far:
SCP-049 Health | Seconds until resurrection is complete
1700 hp        | 13 seconds
1550 hp        | 11 seconds
1275 hp        | 7 seconds
 850 hp        | 4 seconds
 450 hp        | 2 seconds
   1 hp        | 1 second

The seconds aren't perfect because I had to time them in my head instead of objectively with a timer.
It seems to be exponential and not linear. I've tried writing out an equation on a piece of paper but I wasn't able to figure it out.
How can I create a rough equation that's close enough to these ratios to be replicated?

REPLY [3 votes]: Based on the power model
$$y=a +b\,x^c$$ we can find (using nonlinear regression)
$$a=1.20472 \qquad b=8.0561\times 10^{-7} \qquad c=2.21806$$ and this corresponds to $R^2=0.998985$ and $SSQ=0.365$.
$$\left(
\begin{array}{ccc}
x & y & y_{calc} \\
 1700 & 13 & 12.9928 \\
 1550 & 11 & 10.8089 \\
 1275 & 7 & 7.43234 \\
 850 & 4 & 3.73834 \\
 450 & 2 & 1.82288 \\
 1 & 1 & 1.20472
\end{array}
\right)$$
Based on the exponential model
$$y=a+b\, e^{c x}$$
$$a=-0.425564 \qquad b=1.37329 \qquad c=1.34804\times 10^{-3}$$ and this corresponds to $R^2=0.999416$ and $SSQ=0.210$ (better than the previous one).
$$\left(
\begin{array}{ccc}
x & y & y_{calc} \\
 1700 & 13 & 13.1582 \\
 1550 & 11 & 10.6714 \\
 1275 & 7 & 7.23402 \\
 850 & 4 & 3.89352 \\
 450 & 2 & 2.09335 \\
 1 & 1 & 0.94958
\end{array}
\right)$$


TITLE: Calculating max points able to be placed inside a hypercube
QUESTION [2 upvotes]: Given a hypercube of width W, how can I figure out the maximum number of points I can place inside the hypercube such that each point is at least equal to or further than euclidean distance X away from each other.
My ultimate goal is to go backwards and be able to specify the max number of points and generate the required distance.

REPLY [2 votes]: The following construction may be useful. It is not guaranteed to be optimal, because there are border effects, shaping effects and such. IIRC the densest lattice packing is the $D_4$-lattice (our library wanted their copy of Conway & Sloane back, so I cannot check). Here's the description. Specify a scale parameter $d$. Select points with coordinates $d(n_1,n_2,n_3,n_4),$ where $n_1,n_2,n_3,n_4$ are integers subject to the constraint that their sum must be even. Then the closest distance between two such points is $X=\sqrt{2}d$. The number of points $N$ in your hypercube would then be $N\approx \frac12 \left(\frac Wd\right)^4$.
Caveats: I may remember some things wrong, and the $D_4$ lattice is optimal with respect to some other figure of merit. Also, for some choices of $X$ (particularly when $d$ is relatively large with respect to $W$) you may benefit from jiggling the points around a bit and/or rotating the lattice. If my basic recollection is correct, then I doubt you can win much by such tricks, so if this simple, relatively easy to implement construction is good enough for your purposes, you may consider using it.
In full generality your problem probably cannot be answered. I mean, if you specify $W$ and $X$ (resp. $N$), the answer to the question of best $N$ (resp. $X$) may be unknown (read: very difficult).


TITLE: Model for soil temperature underground using the Heat Equation
QUESTION [1 upvotes]: Assuming that the temperature in the ground is a function of time $t$ and depth $x$ only and assuming that at x=0, ground level, the approximate temperature at the surface is
$$u(0,t) = T_{0}+A_{0}\cos(\omega t),$$
where $T_{0}$ is the average temperature, $A_{0}$ is the amplitude of the seasonal temperature variation, and $\omega$ the frequency such that
$$\omega = \frac{2\pi}{year}=\frac{2\pi}{31557341}s^{-1}\approx1.991 \times 10^{-7}s^{-1}.$$
Also assuming that the temperature satisfied the heat equation
$$\frac{\partial{U}}{\partial{t}}={\kappa}^2 \frac{\partial^2{U}}{\partial{x^2}}, $$
For convenience we introduce a temperature deviation $U(x,t)=u(x,t)-T_{0}$. With the one boundary that $$U(0,t)=A_{0}\cos(\omega t)$$
We are only interested in periodic solutions of the form:
$$U(x,t)=V(x)\cos(\omega t) + W(x)\sin(\omega t).$$
How may I show that we may regard $U$ to be the real part of the complex function $\tilde{U},$ $$\tilde{U}(x,t)=X_{(x)}e^{i\omega t},$$ where $X$ may be complex, and show that $\tilde{U}$ obeys the heat equation
$$\frac{\partial{\tilde{U}}}{\partial{t}}={\kappa}^2 \frac{\partial^2{\tilde{U}}}{\partial{x^2}}$$
with boundary condition given by $$\tilde{U}(0,t)=A_{0}e^{i \omega t}.$$
Thank you for any guidance you can give me.

REPLY [1 votes]: If you view this question by power series method approach, you will find that it is very easy to solve.
Similar to Free Schroedinger equation:
Let $u(x,t)=\sum\limits_{n=0}^\infty\dfrac{x^n}{n!}\dfrac{\partial^nu(0,t)}{\partial x^n}$ ,
Then $u(x,t)=\sum\limits_{n=0}^\infty\dfrac{x^{2n}}{(2n)!}\dfrac{\partial^{2n}u(0,t)}{\partial x^{2n}}+\sum\limits_{n=0}^\infty\dfrac{x^{2n+1}}{(2n+1)!}\dfrac{\partial^{2n+1}u(0,t)}{\partial x^{2n+1}}$
$=\sum\limits_{n=0}^\infty\dfrac{x^{2n}}{\kappa^{2n}(2n)!}\dfrac{\partial^nu(0,t)}{\partial t^n}+\sum\limits_{n=0}^\infty\dfrac{x^{2n+1}}{\kappa^{2n}(2n+1)!}\dfrac{\partial^{n+1}u_x(0,t)}{\partial t^n}$
$=\sum\limits_{n=0}^\infty\dfrac{x^{2n}}{\kappa^{2n}(2n)!}\dfrac{\partial^n(T_0+A_0\cos\omega t)}{\partial t^n}+\sum\limits_{n=0}^\infty\dfrac{x^{2n+1}}{\kappa^{2n}(2n+1)!}\dfrac{\partial^{n+1}u_x(0,t)}{\partial t^n}$
$=T_0+\sum\limits_{n=0}^\infty\dfrac{(-1)^nA_0\omega^{2n}x^{4n}\cos\omega t}{\kappa^{4n}(4n)!}-\sum\limits_{n=0}^\infty\dfrac{(-1)^nA_0\omega^{2n+1}x^{4n+2}\sin\omega t}{\kappa^{4n+2}(4n+2)!}+\sum\limits_{n=0}^\infty\dfrac{x^{2n+1}}{\kappa^{2n}(2n+1)!}\dfrac{\partial^{n+1}u_x(0,t)}{\partial t^n}$


TITLE: Least square method solution for constant
QUESTION [0 upvotes]: I would like to ask, why method of least square approximation (A*x=b) gives us solution, that is equal 1/n, where n is number of unknown elements.
example:
Let A =
$\begin{bmatrix} 7 & 7 & 7\\ 7 & 7 & 7 \\ 7 & 7 & 7\\ 7 & 7 & 7\end{bmatrix}$ and b=$\begin{pmatrix} 7\\7 \\7\\7\end{pmatrix}$

Why are then components of vector x equal to 0.33 (1/3). I understand that this would be minimal squared distances between points and new function, but I don't know how to give proof for it (that components of vector x are equal and they are x equal to 1/(number of components)

REPLY [0 votes]: The method of ordinary least squares will not yield the solution $x=(\frac13, \frac13, \frac13)$ as the system is under-determinate.
This solution will be obtained from the pseudo-inverse of the matrix, a more powerful tool. It selects the minimum norm solution among all those possible.
See https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse


TITLE: How to reduce higher order linear ODE to a system of first order ODE?
QUESTION [3 upvotes]: Is there any general and systematic way of reducing the higher order linear ODE to a system of first order ODE?
For example, assume we have $a_3x^{(3)}+a_2x^{(2)}+a_1x^{(1)}+a_0x=0$, then how do we convert this into matrix form(a system of first order ODE). And after we solve the system of equation, how to combine them into our final solution $x(t)$?
Thanks for helping me out!

REPLY [3 votes]: Starting with
$$
x^{(n)}=f(t,x,x',x'',\ldots,x^{(n-1)}),
$$
you get the system
\begin{align*}
x_1&=x\\
x_1'&=x'=x_2\\
x_2'&=x''=x_3\\
&\ldots\\
x_{n-1}'&=x^{(n-1)}=x_{n}\\
x_n^{'}&=x^{(n)}=f(t,x_1,x_2,\ldots,x_{n-1})
\end{align*}