User nick s - MathOverflow

Answer by Nick S for Locally compact abelian groups

2011-02-07T01:06:14Z

I am not too familiar to Lie groups, but I think that your claim can follow from the following Theorem which is proven in Rudin:

If A is locally compact abelian group, then there exists a loc.cpct.abelian group $H$ such that $A$ is isomorphic to some $R^k \times H$, and $H$ contains an open compact subgroup $K$.

Reference: This is on page 95 in Deitmar Echterhoff "Principles of Harmonic Analysis", see also http://mathoverflow.net/questions/70916/when-does-a-lca-group-not-contain-a-closed-infinite-cyclic-subgroup.

Answer by Nick S for Generalizing a problem to make it easier

2010-12-14T00:34:53Z

Here is another of my favourite examples:

Prove that $({\mathbb R},+)$ and $({\mathbb R}[x],+)$ are isomorphic as abelian groups.

It is fairly easy to prove that they are actually isomorphic as ${\mathbb Q}$-vector spaces, which is a stronger result; other than that I don't know any way of proving this.

Answer by Nick S for How to find the almost period of an exponential polynomial

2011-03-26T01:30:53Z

You are basically interested in what is called $\epsilon$-dual Characters.

For a set $\Lambda \subset \R^d$ we define

$$\Lambda^\epsilon := { t \in \R^d | \left| e^{2 \pi x \cdot t} -1 \right| < \epsilon \, \forall x \in \Lambda }\,.$$

In your case $\Lambda := { \lambda_1, .., \lambda_n }$ and for all $t \in \Lambda^\epsilon$ you get

$$\| T_tu - u\|_{\infty} < (|c_1|+...+|c_n|) \epsilon \,.$$

Here is a short review of what is known about $\Lambda^\epsilon$:

1) If $\Lambda \subset \R^d$ is finite, then $\Lambda^\epsilon$ is relatively dense for all $0< \epsilon <2$. , that is $\Lambda^\epsilon +K_\epsilon = \R^d$ for some compact $K_\epsilon$. How to finding this $K$ is exactly waht you need. I will address this question below (*).

2) If $\Lambda \subset \R^d$ is relatively dense and $\Lambda-\Lambda := { x-y | x,y \in \R^d }$ is uniformly discrete (i.e. $|z_1-z_2| > \delta$, for all $z_1, z_2 \in \Lambda- \Lambda$) then $\Lambda^\epsilon$ is relatively dense for all $0< \epsilon <2$. Such a set is called a {\bf Meyer set}.

(*) How do we actually find $K$ so that $\Lambda^\epsilon +K= \R^d$? This is covered by Meyer in the book mentioned below, when he studies the connection between $\Lambda^\epsilon $ relatively dense and $\Lambda$ being harmnious.

I will explain directly what happens in your case, since in general things are a little more complicated.

First lets observe that if $t= \frac{2pi n}{ \lambda}\, n \in \Z$ then $e^{2 \pi \lambda \cdot t} =1 $, which is the reson the problem is easy for latices.

If we only have 2 $\lambda$'s, here is what we need to do: First if $\lambda_1/\lambda_2$ is rational, then the intersection of the latices $ \frac{2pi}{ \lambda_1}\Z \cap \frac{2pi}{ \lambda_2}\Z$ is non-empty and any $t$ in here will do.

If $\lambda_1/\lambda_2$ is irrational, then the latices $ \frac{2pi}{ \lambda_1}\Z$ and $\frac{2pi}{ \lambda_2}\Z$ come arbitrarily close within a fixed gap, and that will do.

More exactly, fix a $\alpha$ so that if $|x-y| < \alpha $ then $ \left| e^{2 \pi x \cdot \lambda_i} -e^{2 \pi y \cdot \lambda_i} \right| < \epsilon$, and then the dirichclet theorem tells you that there exists number $N$ so that you can find integers $m,n$, with $m$ in any interval of length $N$ so that:

$$ | m\frac{2pi}{ \lambda_1} - n\frac{2pi}{ \lambda_2} | < \alpha \,.$$

Then $m\frac{2pi}{ \lambda_1}$.

If you have more than two $\lambda$'s, exactly as above all you have to do is prove that there exists a number $N$ so that within any interval of lenght $N$ there exists a $t$ so that for all $i$ we have:

$$ | t- n_i\frac{2pi}{ \lambda_i} | < \alpha \,.$$

This is what Meyer calls a Harmnious set, and a stronger version of Dirischlet Theorem proves it.

I recommend to you the following book(s):

-Y. Meyer, Algebraic numbers and Harmonic Analysis.

-R. V. Moody - Meyer Sets and their duals.

Answer by Nick S for Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I

2011-02-04T22:50:52Z

Here is an elementary solution:

Let $a_1=(\cos(\theta), \sin(\theta))$ then $a_i= \cos(\theta+\frac{2(i-1)\pi}{n}), \sin(\theta+\frac{2(i-1)\pi}{n})$ thus

$$a_i a_i^T= \left( \begin{array}{c c} \cos^2(\theta+\frac{2(i-1)\pi}{n}) & \cos(\theta+\frac{2(i-1)\pi}{n})\sin(\theta+\frac{2(i-1)\pi}{n}) \\ \cos(\theta+\frac{2(i-1)\pi}{n})\sin(\theta+\frac{2(i-1)\pi}{n}) & \sin^2(\theta+\frac{2(i-1)\pi}{n}) \\ \end{array} \right)$$

Now the result follows imediatelly from the simple trig identities

$$\sum_{i=1}^n \cos^2(\theta+\frac{2(i-1)\pi}{n})= \sum_{i=1}^n \sin^2(\theta+\frac{2(i-1)\pi}{n}) =n/2$$

$$\sum_{i=1}^n \cos(\theta+\frac{2(i-1)\pi}{n})\sin(\theta+\frac{2(i-1)\pi}{n})=\frac{12}{2} \sum_{i=1}^n \sin(2\theta+\frac{4(i-1)\pi}{n})=0 \,.$$

The last question in the problem is equivalent to the following:

Does

$$\sum_{i=1}^n \cos^2(\theta_i)= \sum_{i=1}^n \sin^2(\theta_i) =n/2$$

$$ \sum_{i=1}^n \sin(2\theta_i)=0 \,.$$

imply

$$ \sum_{i=1}^n \sin(\theta_i)=\sum_{i=1}^n \cos(\theta_i)=0 \,?$$

P.S. Can anyone fix my matrix?

Answer by Nick S for How many winning configurations can you have in a nxn Tic-Tac-Toe game where players win if a they get n/2 in either a row or column, consecutively.

2011-01-31T08:07:39Z

If I am not mistaken, it is easy to see that the number is even, at least in the case $n$ even (for n odd, if the strategy matter, it could make a difference).

If $n$ is even than the winning possitions are symmetric with respect to reflection in the centre of the table, and we can use this symmetry to split them in pairwise disjoint pairs; thus it is even.

If $n$ is odd and $"n/2"$ is even, the winning possitions are still symmetric in reflection in the centre of the table, and no winning possition is invariant under this reflection, so again one can split them in pairs.

If $n$ is odd and $"n/2"$ is odd, the winning possitions are still symmetric in reflection in the centre of the table, but we get $4$ winning strings (horisontal, vertical, and two diagonal ones, with the middle exactly in the centre of the table) which are invariant under reflection. Excepting these winning possitions containing one of the $4$ winning strings, everything else can be paired.

For the symmetric posstions containing one of the $4$ winning strings, rotation by $\pi/2$ pairs the ones with horisontal winning string with the ones with vertical winning string, and those with the winning string on one diagonal with the winning string on the other diagonal.

EDIT: Fixed the last case. I wonder if a direct rotation by $\pi_2$ doesn't do directly the trick in all three casess. Rotation by $\pi$ leads to a nicer argument in the first two cases.

Answer by Nick S for Cool problems to impress students with group theory

2011-01-28T18:33:42Z

One of my favourite easy group theory problems:

Any prime number $p$ divides $f_{2p(p^2-1)}$, where $f_n$ is the Fibonacci sequence.

Proof: Let

$$G:= \{ A \in M_2 (Z_p) | \det(a)= \pm1 \}$$

and let

$$F=\left( \begin{array}{c c} 1 & 1 \\ 1 & 0 \\ \end{array}\right) $$

Then $F \in G$ and $G$ is a group of order $2p(p^2-1)$.

Thus

$$\left( \begin{array}{c c} f_{n+1+2p(p^2-1)} & f_{n+2p(p^2-1)} \\ f_{n+2p(p^2-1)} & f_{n+2p(p^2-1)-1} \end{array}\right)$$

$$= F^{n+2p(p^2-1)}= F^n = \left( \begin{array}{c c} f_{n+1} & f_{n} \\ f_{n} & f_{n-1} \end{array}\right) \mod p \,.$$

P.S. Better periods can be obtained by solving the linear reccurence in $Z_p$ if $p =\pm1 \mod 5$ or in an algebraic extension if $p =\pm 2 \mod 5$, but that's exactly the same thing as calculating the order of the matrix $F$ by diagonalizing it.

The same idea can be used for any linear recurrence, but one has to replace $G$ by $GL_2(Z_p)$, and discuss the cases when $p$ divides or doesn't divide the free term of the polynomial associated to teh recurrence.

PPS: Can anyone please fix my matrices.

Answer by Nick S for Decidability of tiling R^2

2011-01-27T23:00:09Z

If I remember right any Turing machine can be translated into a set of Wang tiles, so that the tiling problem for this set of tiles is equivalent to the decibility of the turing machine.

Assuming the non-existence of an aperiodic set of tiles, Wang provided the Decidability of any tiling problem in R^2. Since this is not possible, it basically proves the existence of aperiodic tiles.

So the general decidability problem turned out to be equivalent to the non-existence of an aperiodic set of tiles , which suggests that the decidability problem for 1 tile might be equivalent to the non-existence of an aperiodic 1 tile. I wonder if the Wang theorem can be changed to prove this, could be a starting point.

Such a tile is called an Eistein tile, and if I remember right the problem of its existence was open until few months ago, but it was reported recently that one was found...

Answer by Nick S for Riemann Hypothesis

2011-01-25T05:55:04Z

If you are looking for the connection between quasi-crystals and RH, here is what I remember (I might be wrong):

Take all the zeroes of the zeta function and project them on the critical line. Then the RH is equivalent to this set being pure point diffractive (usually this is what people understand by quasi-crystals, bu the formal definition of a quasi-crystal is intentionally vague).

From what I remember the discrete component of the diffraction is well known, the question about the continuous diffraction spectrum is open (and seems equivalent to the RH).

Answer by Nick S for Mathematical "urban legends"

2011-01-24T22:25:52Z

There is also the story of the young mathematician which speaks in a conference, and at the end of his talk a (famous) mathematician provides a counterexample to his main theorem. This is just another variation to the story posted by WW.

I head this story from couple people (they claim they were there), but, if I recall right, I also read it in "The Puzzling adventures of Dr. Ecco".

Answer by Nick S for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

2011-01-23T00:28:39Z

(Most of the things I post have already been covered in the previous answers, but not combined this way).

Here is my view of the problem:

Given a finite sequence of numbers $a_1,...,a_n$ we can use the Lagrange interpolation formula to get a polynomial $P(x)$ so that $a_k=P(k) \forall k \leq n$.

As yuan mentions this is an unique answer in the following two (equivalent) ways: - The only polynomial of degree at most $n-1$ which fits this data - The polynomial of smallest degree which fits this data.

Now pick a function $f : R \rightarrow R$ {\bf at random}. Let $g(x)= P(x)+ (x-1)(x-2)...(x-n)f(x)$.

Then $g(1)=a_, ..., g(n)=a_n$, and this provides uncountably many different ways of continuing $a_1,...,a_n$.

Second point:

Pick an $x$ at random. Isn't then any "natural" way of continuing the sequence $a_1,...,a_n, a_{n+1}=x$ also in some sense a "natural" way of continuing $a_1,...,a_n$?

But each choice of $x \in R$ leads to a different answer...

Comment by Nick S

2013-05-07T19:06:06Z

(ii) $\Lambda$ is relatively dense, uniformly discrete and $\Lambda-\Lambda \subset \Lambda+F$ for some finite set $F$..... It is somehow surprising, but one (hence both) of these conditions imply that $\supp(\mu_d)$ is relatively dense. In general Meyer sets have also non-trivial $\mu_c$.

Comment by Nick S

2013-05-07T19:04:43Z

2) While characterizing all point sets with these properties is hard, "geometric" conditions which imply each of them are known. Regular model sets are obtained from higher dimensional lattices and they always have $\mu_c=0$... Their subsets, Meyer sets can be characterized by one of the following two equivalent definitions (there are actually more, but I left the rest out): (i) $\Lambda$ is relatively dense and $\Lambda-\Lambda:=\{ x-y| x,y \in \Lambda\}$ is uniformly discrete.

Comment by Nick S

2013-05-07T18:59:52Z

Just few comments: 1) $\mu_d \neq 0$ is not a good condition and I don't think Hof used it. The problem with it is that $\mu_d(\{ 0 \}) = (\dens (N) )^2$ so, unless N is trivial, $\mu_d \neq 0$. The usual two conditions we use are (i) $\mu_c =0$ or the weaker (ii) $\supp(\mu_d)$ is relatively dense. Also, in that paper Hof showed that thermal motion always induces some nontrivial $\mu_c$, thus $\mu_c=0$ is not really the right definition unless you work at 0K.

Comment by Nick S

2012-11-09T23:07:40Z

... small translations of the points... And there are of course uncountably many models which are not associated to PV numbers....... Another issue is that the zeroes of the RZF are not a Delone set, so anything done so far by the quasi-crystal community is not relevant to the problem... And last, I really don't see how one can go around the following issue: Let $\Lambda$ be the set of zeroes. Let $\Lambda'$ be the set obtained by moving all the zeroes, such that the $n$'th zero is moved by at most $\frac{1}{n}$. Then diffraction cannot differentiate between $\Lambda$ and $\Lambda'$.

Comment by Nick S

2012-11-09T23:02:49Z

... cont. I really ahve no idea what he mean by "it is well known that "a unique quasi-crystal exists corresponding to every P- V number". The existence is true, the uniqueness is far for true... Unless I make a terrible mistakes, there are constructions which produce pure point diffractive sets from PV numbers, and they produce uncountably many... In many situations, but not always, one can probably get that most of them are "eqiuavalent" in some sense, but not all of them... And the big issue is that any equivalence in this sense, unless one adds very strong extra conditions, allows for

Comment by Nick S

2012-11-09T22:54:14Z

Well his definition of quasi-crystals is not the one used by the quasi-crystal community (we actually don't have a formal mathematical definition yet).... His statement about icosahedral group is false, actually most 3-dimensional models don't have any symmetry group. Same issue for the 2 dimensional quasi-crystals, most of them are not related to polygons in the plane. And now lets move to the actual important point, what he said so far is irrelevant to the RH question (but shows that he probably learned about them from a non-expert).... So 1-dim quasi-crystals....

Comment by Nick S

2011-04-07T21:49:34Z

Or $$ \begin{bmatrix} 1 & 1 & 4 \\ 1 & -1 & 2 \\ 1 & 1 & 1 \end{bmatrix} $$

Comment by Nick S

2011-03-13T01:38:25Z

There are two things unclear in the problem: 1) Can the cop skip a move? i.e. Does he have to move any turn, or if this is his best move he stays put in one turn? If the answer is yes, the bipartite graphs are not a problem anymore. 2) What happens if the cop and robber walk on the same edge in opposite direction? Did the cop catch the rober or did he got away?

Comment by Nick S

2011-03-12T21:41:14Z

$f^{-1} ( [\delta, 1] ) $ In general, to denote the set of elements $x$ so that $f(x) \in C$ we use $f^{-1}(C)$.

Comment by Nick S

2011-03-11T01:17:53Z

$\alpha$ has to be irational.

Comment by Nick S

2011-02-27T17:31:30Z

$P(x)$ has its zeros all being pure imaginary or zero if and only if $P(ix)$ has all its zeroes real. Thus your problem is equivalent to the one of deciding wheter a polynomial with all coeficients in $Z \cup iZ$ has all roots real.

Comment by Nick S

2011-02-14T22:59:14Z

One more comment: the sum of teh digits completely solves the problem in the case $y=000000.000$ or $y=11111...1$. You could try the following procedure, but this is basically just the standard comparison: Look at $y$ and for each 1 switch the digits in that possition in all $x$ in your code. But this is probably more expensive than studing the Hamming distance.

Comment by Nick S

2011-02-14T22:53:56Z

One thing which could help is looking to the sum of the digits $s(x)$ of each number. If for a number $x$ you have $|s(x)-s(y)| >k$ for sure $x$ is not good. This should eliminate many $x$ from your search. If you are lucky and for some $x$ you get $s(x)+s(y) \leq k$ or $s(x)+s(y) \geq 2n-k$, then you are done: $x$ works.

Comment by Nick S

2011-02-13T18:15:16Z

Fix a non-measurable set $A$. Then for any measurable set $B$, the set $A \Delta B$ is not measurable. This way you get a one-to-one function from the set of measurable sets to the set of non-measurable sets, which shows that there are at least as many non-measurables as measurables.

Comment by Nick S

2011-02-12T06:02:36Z

I think the problem is harder than that Gerhard. Think about a number like 22228 ;)

User nick s - MathOverflow

Answer by Nick S for Locally compact abelian groups

Answer by Nick S for Generalizing a problem to make it easier

Answer by Nick S for How to find the almost period of an exponential polynomial

Answer by Nick S for Prove: if a1,...,an are uniformly distributed unit vectors, then a1*a1'+...+an*an'=n/2*I

Answer by Nick S for How many winning configurations can you have in a nxn Tic-Tac-Toe game where players win if a they get n/2 in either a row or column, consecutively.

Answer by Nick S for Cool problems to impress students with group theory

Answer by Nick S for Decidability of tiling R^2

Answer by Nick S for Riemann Hypothesis

Answer by Nick S for Mathematical "urban legends"

Answer by Nick S for Is there a theorem that says that there is always more than one way to "continue a finite sequence"?

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Comment by Nick S

Answer by Nick S for Prove: if a1,...,an are uniformly distributed unit vectors, then a1a1'+...+anan'=n/2*I