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 ...


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 ...


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{\...


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: $$...


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 ...


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. ...


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*}


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}^{...


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)}...


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_{\...


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 ...


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 ...


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$.


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 ...


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$.


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 ...


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}$...


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