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

 
discard

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

Browse other questions tagged or ask your own question.