52

There are two principles at play here: a mathematical principle that favors hexagonal networks, and a physical principle that favors a network with straight walls.
The mathematical principle that prefers hexagonal planar networks is Euler's theorem applied to the two-torus $\mathbb{T}^2$ (to avoid boundary effects),
$$V-E+F=0,$$
with $V$ the number of ...

answered Jun 6 '20 at 14:14

Carlo Beenakker

132k1212 gold badges324324 silver badges461461 bronze badges

48

There is the following result of Davenport, Lewis, and Schinzel [DLS64, Cor to Thm 2]:
Theorem. Let $p \in \mathbf Z[x]$. Then the following are equivalent:
$p$ is a sum of two squares in $\mathbf Z[x]$;
$p(n)$ is a sum of two squares in $\mathbf Z$ for all $n \in \mathbf Z$;
Every arithmetic progression contains an $n$ such that $p(n)$ is a sum of two ...

ag.algebraic-geometry nt.number-theory ac.commutative-algebra polynomials oc.optimization-and-control

answered May 29 '20 at 4:56

R. van Dobben de Bruyn

18.5k22 gold badges6060 silver badges102102 bronze badges

34

$\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\epsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\Si}{\Sigma}
\newcommand{\thh}{\theta}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\E}{\operatorname{\mathsf E}}
\newcommand{\PP}{\operatorname{\mathsf P}}
\newcommand{\...

pr.probability probability-distributions oc.optimization-and-control real-algebraic-geometry moments

25

There is this theorem of Thomas Hales from 1999, which proves the Honeycomb Conjecture:
Theorem.
Let $\Gamma$ be a locally finite graph in $\mathbb{R}^2$, consisting of smooth curves, and such that $\mathbb{R}^2\setminus \Gamma$ has infinitely many bounded connected components, all of unit area. Let $C$ be the union of these bounded components. Then
$$
\...

17

The minimum must occur at vectors $x,y$ where
$x_i$ and $y_i$ take only two values each.
This should make it easy to check Neil Strickland's
experimental result (where $x$ and $y$ are indeed of this form).
[EDIT: see the answer by Adam P. Goucher for this check.]
It is convenient to extend $A$ homogeneously to all nonzero $x,y$
in the zero-sum hyperplane:
$$...

answered Oct 10 '18 at 15:02

Noam D. Elkies

69k1212 gold badges246246 silver badges331331 bronze badges

15

The classical result is the celebrated Sard-Smale Theorem, see 1.
Theorem (Smale). Let $\phi \colon B \longrightarrow M$ be a $C^q$-Fredholm map between separable Banach manifolds, with $q > \max \{0, \, \textrm{index of } \phi\}$. Then the set of regular values of $\phi$ is residual in $M$.
Here residual set means that it is a countable intersection ...

reference-request dg.differential-geometry fa.functional-analysis ca.classical-analysis-and-odes oc.optimization-and-control

answered May 15 '15 at 9:13

Francesco Polizzi

59.6k55 gold badges165165 silver badges257257 bronze badges

14

There is the concept of hyperbolic programming, introduced in the 90's by Osman Güler:
O. Güler, Hyperbolic Polynomials and Interior Point Methods for Convex Programming, Math. Oper. Res. 22 (1997) 350-377.
See also
H.H. Bauschke, O. Güler, A.S. Lewis, H.S. Sendov, Hyperbolic Polynomials and Convex Analysis, Canad. J. Math. 53 (2001) 470-488;
J. ...

answered Feb 22 '16 at 20:28

Pedro Lauridsen Ribeiro

5,69411 gold badge2424 silver badges5454 bronze badges

14

Experimental investigation suggests that the minimum is $n/(n-1)$, attained when
\begin{align*}
x &= (1-n,1,1,\dotsc,1)/\sqrt{n^2-n} \\
y &= (1,1-n,1,\dotsc,1)/\sqrt{n^2-n} \\
\end{align*}

answered Oct 7 '18 at 10:01

Neil Strickland

46.7k77 gold badges123123 silver badges219219 bronze badges

13

There has been recently a flurry of new results on provable nonconvex methods which can be guaranteed to converge to the global optimum. In other cases, the non-convex problem itself is shown to have no spurious local optima. The classical case is the singular value decomposition (SVD) which is non-convex but yet solvable. This is because only the top ...

13

This topic has long history. Here are some references:
Bloch, Anthony M. "Steepest descent, linear programming and Hamiltonian flows." Contemp. Math. AMS 114 (1990): 77-88.
Brockett, Roger W. Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems. Decision and Control, 1988., Proceedings of the 27th IEEE Conference on. ...

12

The upper bound is not correct. E.g., let $n=101$, $x_1=\dots=x_{100}=1/1000$, $x_{101}=9/10$. Then
$$\left(\prod_{i=1}^{n}x_{i}^{x_{i}}\right)\left(\sum_{i=1}^{n}x_{i}^{1/2}\right)^{2}>7>2.$$
More generally, take any $a\in(0,1)$ and any natural $k$, and then let $n=k+1$, $x_1=\dots=x_k=a/k$, $x_{k+1}=1-a$. Then
$$\ln\left[\left(\prod_{i=1}^{n}x_{i}^{...

answered Apr 12 '16 at 14:24

Iosif Pinelis

62.1k44 gold badges5959 silver badges117117 bronze badges

12

I will prove the original inequality.
First, performing the change of variables $x=1/a$, etc., and inverting the harmonic mean, we need
$$
\sum \left|\frac{yz}{x(y+z-x)}\right|\geq \frac32.
$$
Next, denoting $p=y+z-x$, etc., we transform the inequality to
$$
\sum\left|\frac{(p+q)(p+r)}{p(q+r)}\right|\geq 3,
$$
or
$$
\sum\left|2+\frac{(p-q)(p-r)}{p(q+r)}...

real-analysis inequalities oc.optimization-and-control nonlinear-optimization real-algebraic-geometry

11

Sorry, I'm still not allowed to comment. So I use the "Answer" window...
I'm not completely sure to understand your formulation, but for the case of a 2-dimensional sphere and some fixed width of the pealing, you may find your answer in the sphere-filling ropes of Gelrach and von der Mosel. These are ropes with a certain fixed width that are going on a ...

11

Write $V(a)$ for the determinant $\prod_{0\leq i<j\leq n-1} |a_i-a_j|$. Selberg's formula tells you that
$$\int_0^1 \cdots \int_0^1 V(a)^{2\beta} \prod_{i=0}^{n-1} da_i=
n! \prod_{j=0}^{n-1} \frac{(\Gamma(1+j\beta))^2 \cdot \Gamma((j+1)\beta)}
{\Gamma(2+(n+j-1)\beta)\cdot \Gamma(\beta)}=:A(n,\beta)$$
Thus the asymptotics you seek are given by $\lim_{\...

ca.classical-analysis-and-odes oc.optimization-and-control asymptotics determinants legendre-polynomials

11

There is a (nearly) trivial linear-time lower bound, because it takes linear time to read in the input. (I say this is nearly trivial because you do have to argue that it is necessary to examine at least a constant fraction of the input to get the right answer.)
Some slightly super-linear time bounds are known, under certain assumptions about the ...

graph-theory mg.metric-geometry computational-complexity oc.optimization-and-control traveling-salesman-problem

answered Nov 12 '17 at 18:19

Timothy Chow

58.3k1919 gold badges258258 silver badges440440 bronze badges

11

To answer on methods applicable here (and elaborate on comments I made). The most promising is to use a surprisingly little-known theorem that says that the discriminant $D$ of a symmetric $n\times n$ matrix $A=(a_{ij})$ with eigenvalues $\lambda_1,\dots,\lambda_n$, i.e.
$$ D_A=\prod_{1\leq i<j\leq n} (\lambda_i-\lambda_j)^2,$$
is a sum of squares in the ...

10

The rigorous mathematical context is stability. A straight rope in either tension or compression is a valid solution of the underlying PDE, but in compression this solution is unstable, so it cannot be realized in practice.

10

The Carleton College library has a copy of the Kushner book. Here's the theorem:
Theorem 8
Let* $P\gt0, C\ge0$ and
$$EA_n'PA_n-P=-C.\ \ \ (8.24)$$
Then $EX_n'CX_n\rightarrow0$ and $X_n'CX_n\rightarrow0$ w.p.l. Also
$$P_x(\sup_{\infty\gt n\ge0} X_n'PX_n \ge \lambda) \le {x'Px\over\lambda}.$$
Hence, the ...

10

First of all, there is a general theory (due to Chebyshev) on the best uniform approximation
of ANY continuoius function $f$ by polynomials of degree at most $d$ on an interval.
It describes the polynomial of the best approximation, which is unique.
In Chebyshev's polynomials, $f=x^n$ and $d=n-1$. You are asking about $f=x^n$ and
some given $d<n$. I do ...

answered Aug 23 '15 at 20:35

Alexandre Eremenko

71.6k66 gold badges207207 silver badges343343 bronze badges

10

Isn't it just the 2d sphere packing? If one assumes that the larvae needs a disc of fixed radius to grow up to an adult form and that the bees want to have as many cells as possible then the hexagonal lattice is the optimal one.

10

Write $x = 1-X$, $y=1-Y$, $z=1-Z$. Then the inequality reduces to
$$2XYZ \leq X^2 + Y^2 + Z^2$$
for $X, Y, Z \leq 1$. If $X, Y, Z < 0$ then the inequality is trivial, since LHS < 0. Otherwise suppose $X \in [0, 1]$ wlog. Then
$$\text{RHS} - \text{LHS} = X^2 + (1-X^2)Y^2 + (Z-XY)^2 \geq 0.$$
Equality holds iff $X = Y = Z = 0$.

real-analysis inequalities oc.optimization-and-control nonlinear-optimization real-algebraic-geometry

9

First, let's assume $a=1$; for other values we can scale a solution with $\sqrt{a}$.
So we want to minimize $H=\sum_{i,j} (1-\|x_i-x_j\|^2)^2$.
I globally optimized the problem numerically for $n=4$ and $n=5$ and obtained as solutions
for $n=4$, the square with side length $\sqrt{\frac{2}{3}}\approx0.8165$, giving $H_4=\frac{2}{3}$
for $n=5$, the ...

mg.metric-geometry polynomials oc.optimization-and-control global-optimization nonlinear-optimization

answered Aug 29 '14 at 10:46

Moritz Firsching

9,85722 gold badges5252 silver badges8181 bronze badges

9

Since this is my main area of research, let me attempt an answer (which inevitably got quite long!). The short answer is that I do not know of any specific instances where topological complexity has been used to solve robotics problems, but I know that roboticists are interested in the concept, and am hopeful that such instances may occur in the future.
Let ...

9

That is highly unlikely. Take any such system $S$ of permutations. Take any configuration of points obtained by sampling and note that we can also get it with the points re-enumerated in any way. Now let us look at how many reasonably short path enumerations are there at all. For each short path, there is a sequence of integers $a_1,\dots,a_{n-1}$ with sum $\...

9

By density, it is enough to prove the property when $A$ is positive definite. Then
$$A(I+BA)^{-1}=A^{1/2}(I+A^{1/2}BA^{1/2})^{-1}A^{1/2}$$
is congruent to $(I+A^{1/2}BA^{1/2})^{-1}$, which itself is positive definite because $I+A^{1/2}BA^{1/2}\succeq I$.

answered Feb 26 '18 at 12:26

Denis Serre

44.7k88 gold badges126126 silver badges255255 bronze badges

9

Zebras win for all $N$.
I didn't realize Lawrence's answer in the source is actually sound (or so I think, when I really took some time to read it through this morning). Below I basically adopt Lawrence's strategy for $N$, with schematic drawings to make the argument easier to follow.
The following is a winning starting position for the zebras.
where $a$ ...

9

Here is a classic article by L. Fejes Toth on this subject.
https://projecteuclid.org/euclid.bams/1183526078

9

Here is a paragraph of THE LIFE OF THE BEE (1901) By Maurice Maeterlinck:
"There are only," says Dr. Reid, "three possible figures of the cells which can make them all equal and similar, without any useless interstices. These are the equilateral triangle, the square, and the regular hexagon. Mathematicians know that there is not a fourth way ...

9

It can be $O(n^{\frac32})$ for $a\ge 1$ if the sets $A_i$ correspond to the $p^2$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $\mathbb F_p$ and your points are the $p^3$ general position planes, with $p^2$ planes through each point. There are no 3 collinear points if the surface is chosen appropriately, so for any 3 ...

co.combinatorics oc.optimization-and-control combinatorial-optimization infinite-combinatorics hypergraph

8

Since you know already that the optimal $a_i$ have
$2a_i + 1 = x_i = \pm 1$ and the roots of $P'_{n-1}$,
the calculation of $V_n$ comes down to the discriminant of $P'_{n-1}$,
its leading coefficient, and its values at $\pm 1$, all of which are
available in closed form via formulas for
Jacobia
polynomials (since $P'_{n-1}$ is a multiple of $P^{(1,1)}_{n-2}$...

ca.classical-analysis-and-odes oc.optimization-and-control asymptotics determinants legendre-polynomials

answered Jun 26 '15 at 22:16

Noam D. Elkies

69k1212 gold badges246246 silver badges331331 bronze badges

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

oc.optimization-and-control × 989convex-optimization × 169

nonlinear-optimization × 143

linear-algebra × 124

matrices × 90

linear-programming × 74

pr.probability × 70

global-optimization × 63

reference-request × 59

fa.functional-analysis × 57

mg.metric-geometry × 57

na.numerical-analysis × 56

co.combinatorics × 51

combinatorial-optimization × 47

dg.differential-geometry × 41

graph-theory × 37

algorithms × 37

calculus-of-variations × 34

convexity × 32

real-analysis × 30

inequalities × 30

computational-complexity × 30

stochastic-processes × 29

ds.dynamical-systems × 25

differential-equations × 25