All Questions
1,021 questions
2
votes
1
answer
368
views
Explicit construction of Kakeya sets using Perron tree
I have found many excellent notes online that illustrate how to construct a Kakeya needle set (with measure $<\varepsilon$.) Yet none of them gives full argument about the construction of a Kakeya ...
- 751
1
vote
2
answers
958
views
Integer linear programming (ILP) formulation of connectivity of induced subgraph
Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...
25
votes
1
answer
2k
views
The abc-conjecture as an inequality for inner-products?
The abc-conjecture is:
For every $\epsilon > 0$ there exists $K_{\epsilon}$ such that for all natural numbers $a \neq b$ we have:
$$ \frac{a+b}{\gcd(a,b)}\,\ <\,\ K_{\epsilon}\cdot \text{rad}\...
user6671
12
votes
1
answer
1k
views
Logical completeness of Hilbert system of axioms
This is really a question about references. The entry in Russian Wikipedia about Hilbert's axioms states, in particular, that completeness of Hilbert's system was proven by Tarski in 1951. The ...
- 308
2
votes
1
answer
871
views
Interior point of a convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
2
votes
1
answer
237
views
Sampling algorithms on convex polytopes
Let $f=\mathbf{c}\cdot\mathbf{x}$ be the optimization objective function whose parameter vector $\mathbf{x}\in\mathbb{R}^n$ is subject to the following constraints in the very well-known linear-...
1
vote
0
answers
109
views
Euclid Book 1 Proposition 4 [closed]
In Euclid's The Elements, Book 1, Proposition 4, he makes the assumption that one can create an angle between two lines and then construct the same angle from two different lines. I do not see ...
- 11
0
votes
0
answers
43
views
Minimizing along independent directions, nonlinear programming
Good afternoon, I am studying the book Nonlinear Programming: Theory and Algorithms (by Mokhtar S. Bazaraa, Hanif D. Sherali, C. M.) particularly the Theorem $7.3.5$. I'm not sure I understand this ...
- 193
4
votes
2
answers
493
views
addition theorems for hypersine
I learned from Wolfram MathWorld about hypersine, as being a dimensional analog trig function for hypersolid angles. There it is being defined by
The hypersine ($n$-dimensional sine function) is a ...
6
votes
1
answer
295
views
Does any real projective plane incidence theorem follow from axioms?
Is it known whether any projective geometry statement that holds true in the real projective plane (equivalently, can be deduced from Hilbert axioms) follows from the standard projective axiomatics?
...
- 308
12
votes
2
answers
659
views
The $r$-dimensional volume of the Minkowski sum of $n$ ($n\geq r$) line sets
Let $n$ line sets be $\mathcal{S}_i=\{a\mathbf{h}_i:0 \le a \le 1\}$, for $1 \le i \le n$, where $\{\mathbf{h}_1,\cdots,\mathbf{h}_n\}$ is a vector group of rank $r$ in the $r$-dimensional Euclidean ...
- 550
7
votes
1
answer
453
views
For regular tetrahedron $ABCD$ with center $O$, and $\overrightarrow{NO}=-3\overrightarrow{MO}$, is $NA+NB+NC+ND\geq MA+MB+MC+MD$?
Let $ABCD$ be a regular tetrahedron with center $O.$ Consider two points $M,N,$ such that $\overrightarrow{NO}=-3\overrightarrow{MO}.$ Prove or disprove that
$$NA+NB+NC+ND\geq MA+MB+MC+MD$$
I ...
- 181
2
votes
0
answers
47
views
A linear program where coordinate descent works pretty well
I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...
- 21
5
votes
1
answer
3k
views
Distance between point inside a triangle and its vertices [closed]
How to determine the distance between an arbitrary point inside a triangle and its vertices if side lengths are given. Is there any correlation between these distances or their sum and the lengths of ...
1
vote
1
answer
168
views
Perturbation of the value of a general-sum game at a equilibirium
Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...
- 1,127
11
votes
2
answers
863
views
Strange formula for area of a convex polygon
Consider a convex $n-$gon in $\mathbb{R}^2$ with sides contained in the lines $y=k_ix+b_i, 1\leq i\leq n.$ Then its area equals to
$$
S=\frac{1}{2}\sum_{i=1}^{n} \frac{(b_{i+1}-b_i)^2}{k_{i+1}-k_i}.
$$...
- 4,316
18
votes
2
answers
667
views
Total length of a set with the same projections as a square
Take some convex polygon $P$. I'm mostly asking about the unit square, but would also appreciate thoughts on general polygons. We want to take a family of line segments inside $P$ that have the same ...
- 1,160
4
votes
0
answers
98
views
Collections of points maximally spaced with respect to one another
The icosahedron and dodecahedron are well known to share symmetry groups. This partially accounts for the fact that one can form a type of compound of the two where each of the vertices in the ...
- 3,209
1
vote
0
answers
283
views
total unimodularity of a matrix
Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
- 393
6
votes
4
answers
691
views
Triangle angle bisectors, trisectors, quadrisectors, …
With the triangle
angle bisector theorem
and
Morley's trisector theorem
as background ,
are there any pretty theorems known for triangle $n$-sectors,
$n > 3$?
For example, angle quadrisectors?
The ...
- 151k
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
13
votes
1
answer
374
views
Covering the disk with a family of infinite total measure - the convex sequel
Let $(U_n)_n$ be an arbitrary sequence of open convex subsets of the unit disk $D(0,1)\subseteq \mathbb{R}^2$ s.t. $\sum_{n=0}^\infty \lambda(U_n)=\infty$ (where $\lambda$ is the Lebesgue measure). ...
- 1,461
17
votes
1
answer
569
views
Covering the disk with a family of infinite total measure
Let $(U_n)_n$ be an arbitrary sequence of open subsets of the unit disk $D(0,1)\subseteq \mathbb{R}^2$ s.t. $\sum_{n=0}^\infty \lambda(U_n)=\infty$ (where $\lambda$ is the Lebesgue measure). Does ...
- 1,461
1
vote
1
answer
130
views
find a PSD matrix that that verify matrices sum of equality
$A $, $ C$ $(n,n)$ are symmetric PSD matrices,
$B$ is PD symmetric matrix, and $H_i$ $\; $ $(i=[1,m])$ represent $ m $ complex matrices. $H_i$ are all one rank matrix
Our objectif is to find ...
- 377
2
votes
2
answers
422
views
Algorithm to determine if a union of half-spaces is all of $\mathbb{R}^d$
I have a collection of closed half-spaces $H_1, \dots, H_n \subseteq \mathbb{R}^d$, each given as $H_i = \{x \in \mathbb{R}^d : a_i \cdot x \geq c_i\}$ for some $a_i \in \mathbb{R}^d$ and $c_i \in \...
- 461
34
votes
5
answers
3k
views
Open problems from antiquity solved with analytic geometry
E. T. Bell wrote in Men of Mathematics:
Though the idea behind it all is childishly simple, yet the method of analytic geometry is so powerful that very ordinary boys of seventeen can use it to prove
...
0
votes
1
answer
405
views
Computing discrete optimal transport
I am trying to find a combinatorial approach to solve the following optimization problem.
\begin{align}
&\max_{x_{ij}} C_{ij} x_{ij}, \\
&\text{such that},\\
&\sum_{j} x_{ij} \leq r_i~\...
- 133
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 479
6
votes
3
answers
2k
views
Euler's rotation theorem revisited - Elementary geometric proofs
This is a very elementary topic but I thought it might be worth giving it a try here, I would be very interested in any comments - I originally posted it to Maths SE.
Euler's Rotation Theorem, proved ...
6
votes
1
answer
779
views
If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?
I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
5
votes
1
answer
476
views
Can set-like objects obeying ZFC be constructed in Euclidean geometry?
Is it possible to base set theory on Euclidean geometry, by carefully defining various notions from set theory in terms of geometric objects, so that the ZFC axioms can be shown to hold for them? ...
- 241
3
votes
1
answer
96
views
On the area-perimeter ratio of a convex limited set
(Previously asked on MSE)
Let $C\subset \mathbb{R}^2$ be a convex limited set. We define the average radius of $C$ as
$$a_C=\frac{\int_{v\in C}d(v,C)dxdy}{A(C)}$$
Where $d(v,C)$ is the distance ...
- 377
5
votes
2
answers
355
views
Frégier and Frégier's Theorem
A curious and interesting gem is Frégier's theorem, quoted here from David Wells:
Choose any point $P$ on a conic, and make it the vertex of a right
angle which rotates about $P$. Then the ...
- 3,443
35
votes
6
answers
2k
views
Trigonometry / Euclidean Geometry for natural numbers?
Let $d(a,b) = 1 - \frac{2\gcd(a,b)^3}{ab(a+b)}$ be a metric on natural numbers without $0$.
The metric space $X = \{x_0,x_1,\cdots,x_n\},n>2$ is isometric embeddable in $\mathbb{R}^n$ if and only ...
user6671
-1
votes
2
answers
320
views
A Erdős–Mordell Like inequality
Ono's inequality is true for acute triangle but false with general triangles. The inequality as follows is false with general triangls but I think it true with acute triangle (follows answer by Fedor ...
- 1,776
5
votes
0
answers
142
views
Mordell's theorem on rational quadrilaterals
Mordell proved that for any epsilon and any quadrilateral in the Euclidean plane there is an epsilon-close quadrilateral whose sides and diagonal are rational. Does this break down for five points in ...
- 1,638
1
vote
0
answers
163
views
Can we reduce the maximization of this integral to the maximization of the integrand?
I would like to know whether we are able to reduce the following optimization problem to the pointwise optimization of the integrand (or how we can solve it otherwise): Maximize $$\sum_{i\in I}\sum_{j\...
- 167
0
votes
1
answer
99
views
Finding dual of a scheduling LP formulation
Suppose I have an LP formulation as such:
$\min\ \ \sum\limits_{i,j,t}\ w_{ij}x_{ijt} (\frac{t-r_j}{p_{ij}}+0.5)$
$\sum\limits_{i,t}\frac{x_{ijt}}{p_{ij}}=1\,\forall\ j$
$\sum\limits_{j}x_{ijt}\leq ...
- 103
0
votes
1
answer
113
views
How do I solve this integer programming problem with non convex constraints?
I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.
I have an optimization problem like this
...
- 103
4
votes
0
answers
161
views
Trilinear polarity from AG perspective
Consider a triangle $ABC$ in the projective plane $\mathbb{P}^2.$ For a point $p \in \mathbb{P}^2$ one can define its trilinear polar line $t(p)$ (see here). This defines a birational map to the dual ...
- 4,316
0
votes
0
answers
101
views
How can we analytically solve this max-sum-min problem?
Let $I$ be a finite set, and $A_{ij},B_{ij},x_i,y_j\ge0$. I want to find the choice of $x_i,y_j$ maximizing $$\sum_{i\in I}\sum_{j\in J}A_{ij}\min\left(x_i,B_{ij}y_j\right)\tag1$$ subject to $$\sum_{i\...
- 167
9
votes
0
answers
337
views
Which tetrahedra are scissor congruent to a cube?
Question: Which Euclidean tetrahedra are scissor congruent to cubes?
Consider a Euclidean tetrahedron $T$ in $\mathbb{R}^3$ with edge lengths $l_1,\ldots, l_6$ and dihedral angles $\alpha_1,\ldots, \...
- 4,316
35
votes
1
answer
2k
views
Which polygons can be turned inside out by a smooth deformation?
Take a non-degenerate polygon with side lengths $\{a_1,\dots,a_n\}$ in a convex configuration. What is the condition on the $a_i$'s so that the polygon can be turned inside out by a continuous motion ...
- 4,862
0
votes
1
answer
61
views
Variant of the linear programming problem
Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....
- 193
2
votes
0
answers
70
views
«Euclidean» local systems
The moduli space of G-local systems on a surface is a fundamental object in mathematics. The cases $G=SU(2)$ and $G=SL_2(\mathbb{R})$ are of particular interest. Consider the group $E$ of isometries ...
- 4,316
2
votes
0
answers
148
views
Generalization of Farkas' Lemma to Hermitian Matrices
I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...
0
votes
0
answers
35
views
Converting a vector in a cone statement to inequality constraints
I would like to convert the following condition for $x$
\begin{align}
x = N \lambda, \lambda \geq 0
\end{align}
to a pure linear inequality form, i.e. find an $L$ and eliminate $\lambda$
\begin{...
- 1
1
vote
0
answers
25
views
Weird subspace/equality-constrained LP problem/variant of change-making problem
Assume that we have a set, $\mathscr{R}$ containing $m$-dimensional vectors. Solve
$$\sum_{i=1}^n c_i\leq\delta$$
$$\text{subject to } \sum_{i=1}^n r_i c_i=x^\prime \text{ for all }x^\prime$$
where
$0\...
- 11
6
votes
1
answer
861
views
Is Binary Integer Linear Programming solvable in polynomial time?
The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
- 221
3
votes
1
answer
1k
views
Finding the closest special orthogonal matrix in Frobenius norm sense
Given a $3\times3$ matrix $M$, if we would like to get the closest $\mathrm{SO}(3)$ matrix $R$ that minimizes
\begin{equation}
\|R-M\|_F
\end{equation}
then $R$ = $UV^{T}$ where $U$ and $V^{T}$ are ...
- 33