Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

EDIT: Since posting my original question I have simplified the problem to finding a sufficient condition for $\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$ which is trigonometric semialgebraic in $a,b,\phi$. Trigonometric semialgebraic means given by a system of equalities and inequalities of trigonometric polynomials in the given variables. See the end of this post for the derivation of this fact.

I am attempting to find an effective test for whether or not a set is contained in particular collections of infinitely many semialgebraic sets, as part of a larger inquiry into triangular billiards. In order to do this, I need a sufficient condition that, given the values $A\in SO(2),\vec{x},\vec{y}\in \mathbb{R}^2,c\in \mathbb{R}$, ensures $\vec{x}^TM\vec{y} > c$ has a solution with $M\in S = \{I,A,\ldots,A^{n}\}$ where $n\in\mathbb{N}$ is chosen maximally such that all $X\in S$ satisfy $(0\text{ }1)X(1\text{ }0)^T > 0$. Specifically, I need a condition which is semialgebraic in the entries of $A,\vec{x},\vec{y},c$, meaning it can be expressed as a boolean combination of equalities and inequalities of polynomials in these entries. The chief difficulty in this is that the set $S$ is not semialgebraic in the entries of $A$, as $n$ depends on $A$. There are relatively trivial such conditions which used fixed $k\in\mathbb{N}$, check that $n\geq k$ and test $A,\ldots,A^k$, but these conditions are too strong to be of use to me.

I have found one other such condition, which is that there exists an $M\in SO(2)$ such that $\vec{x}^TM\vec{y} > c \wedge \vec{x}^TMA\vec{y} > c$, which is clearly semialgebraic in the desired variables. It is not hard to see that this is sufficient. Note that as a space $SO(2)$ is homeomorphic to $S^1$ by $h(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\\\ \sin\theta & \cos\theta\end{pmatrix}$. Also, the space of solutions in $SO(2)$ to $\vec{x}^TX\vec{y} > c$ is connected, so consists of the image of $[\theta,\theta + \phi]\subset S^1$ under $h$ for some $\theta,\phi\in S^1$, where an interval in $S^1$ is defined as the image of an interval in $\mathbb{R}$ under the obvious map. Thus if $M$ satisfies the condition, then all elements of $h([\theta,\theta +\phi])$ must satisfy the condition, where $\theta,\phi$ are the angles of rotation of $A$. Additionally, if $M = \begin{pmatrix} \cos\theta & -\sin\theta \\\\ \sin\theta & \cos\theta\end{pmatrix}$ is a solution to $\vec{x}^TM\vec{y} > c$ then $$M^T = \begin{pmatrix} \cos\theta & \sin\theta \\\\ -\sin\theta & \cos\theta\end{pmatrix} = \begin{pmatrix} \cos(-\theta) & -\sin(-\theta) \\\\ \sin(-\theta) & \cos(-\theta)\end{pmatrix}$$ since $\vec{x}^TM^T\vec{y} = \vec{y}^TM\vec{x} = \vec{x}^TM\vec{y}$, so we can assume $0<\theta+\phi < \pi$ by choosing $M^T$ if necessary. Since $h([0,\phi]),h([\phi,2\phi]),\ldots,h([n\phi,(n+1)\phi])$ cover $h([0,\pi])$, one of these images must intersect $h([\theta,\theta +\phi])$, and furthermore because the lengths of images of the intervals $[i\phi,(i+1)\phi],[\theta,\theta +\phi]$ are the same, one of its endpoints must be in $h([\theta,\theta +\phi])$. This endpoint cannot be $(n+1)\phi$ as $(n+1)\phi>\pi>\theta+\phi$, so one of $h(0),h(\phi),\ldots,h(n\phi)$ must be a solution, and this is precisely the set $S$.

However, this condition is still much stronger than necessary. Does any strictly weaker condition exist which is semialgebraic in the entries of $A,\vec{x},\vec{y},c$? And if so, can a sequence of progressively weaker semialgebraic sufficient conditions be devised that satisfies the following:

  1. Any solution to $\vec{x}^TM\vec{y} > c$ with $M\in S = \{I,A,\ldots,A^{n}\}$ satisfies some condition in the sequence.
  2. The condition I gave is strictly stronger than some condition in the sequence.

The second stipulation disqualifies the sequence consisting of the trivial conditions with increasing $k$ described earlier, unless my condition happens to be unsatisfiable for some reason I have overlooked.

EDIT: The problem reduces to finding trigonometric semialgebraic criteria on $a,b,\phi$, with it known that $a,b\in [0,\pi]$, which imply that $[a,b]\cap \{0,\phi,\ldots,n\phi\}\neq \emptyset$, as the entries of $A$ are sines and cosines of $\phi$ and the endpoints of the interval whose image under $h$ satisfies $\vec{x}^TM\vec{y} > c$ (the set of such $M$ is semialgebraic) has entries which are sines and cosines of $a,b$. Further simplifying, we need a trigonometric semialgebraic condition on $a,b,\phi$ which implies that $\frac{\pi}{n\phi}a \leq \frac{k\pi}{n} \leq \frac{\pi}{n\phi}b$ for some $k\in\mathbb{Z}$, i.e. that $\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$. The condition I gave corresponds to the condition that $\frac{b}{\phi}-\frac{a}{\phi}\geq 1$, which is equivalent to $\cos(b-a)\leq \cos(\phi)$. This is satisfied iff $\lfloor \frac{a}{\phi}+x\rfloor \neq \lfloor \frac{b}{\phi}+x\rfloor,\forall x\in [0,1]$. In order to answer my question in the affirmative I need trigonometric semialgebraic conditions which are equivalent to $\lfloor \frac{a}{\phi}+x\rfloor \neq \lfloor \frac{b}{\phi}+x\rfloor,\forall x\in I$, where $I$ is an interval that can be made arbitrarily small. The difficulty in this is that in the proof of my earlier condition I invoke the property that $[a,b]$ has length at least $\phi$ in a crucial way, so a very different approach is required.

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.