User nikita sidorov - MathOverflow

Answer by Nikita Sidorov for Linear numeration systems

2013-02-15T16:47:25Z

Some results on the quantity in question can be found in

J. M. Dumont, N. Sidorov and A. Thomas, Number of representations related to a linear recurrent basis, Acta Arithmetica 88 (1999), 371-394.

We are mainly interested in the summatory function but there are also some upper bounds for the quantity itself. Our main assumption is that the corresponding root (of $x^4=x^3+x^2+x-1$ in your case) is a Perron number (in your example it's even Salem, so our results apply).

Hutchinson's formula for asymptotically homogeneous Cantor sets

2013-01-13T14:10:21Z

As everyone knows, the standard middle-thirds Cantor set is constructed by dividing the interval into three equal parts, removing the middle one, then applying the same procedure to the remaining two intervals, etc.

The resulting set has Hausdorff dimension $s=\log 2/\log 3$, in view of Hutchinson's formula: $$ \sum_{i=1}^m r_i^s=1, $$ where in our case $m=2, r_1=r_2=1/3$.

Now, assume that $m=2$ but that on level $n$ we remove the middle-thirds interval whose relative measure is not exactly $1/3$ but $1/3+\delta_n$, where $\delta_n\to0$ sufficiently fast. (It may also depend on a position of the interval but there is always a uniform upper bound which tends to 0 sufficiently fast.)

Is it still true that the Hausdorff dimension of such a set is $\log2/\log3$?

This is actually a `toy question', since in my set-up the corresponding iterated function system is infinite countable. However, Hutchinson's formula works for such IFS just as well (with $m=\infty$), so I'm sure the conclusion should be the same. If it helps, the uniform upper bound for the $\delta_n$ in my case is a double exponent, i.e., $\frac1n \log (-\log \delta_n)\to \text{const}$ as $n\to+\infty$.

Answer by Nikita Sidorov for When we use Bernstein polynomials in application

2012-12-05T16:17:48Z

The only practical advantage of Bernstein polynomials is their universality. They really work for any continuous function $f$. However, it is well known that if $$ \|f-B_n(f)\|_\infty=o(1/n),\quad n\to\infty, $$ then $f(x)=ax+b$. In other words, one cannot hope to approximate a non-linear function by a Bernstein polynomial with an error term better than $1/n$ - which is impractical.

Answer by Nikita Sidorov for Monic polynomial with integer coefficients with roots on unit circle, not roots root of unity?

2012-11-28T11:32:35Z

Just a couple of minor top-ups to Dmitri's nice answer.

For each even $n\ge2$ the polynomial $p_n(x)=x^n-x^{n-1}-\dots-x+1$ is a Salem polynomial.
It is not known whether for any $\delta>0$ there exists a Salem polynomial such that $\theta<1+\delta$ for its largest root $\theta$ (which is a Salem number). Lehmer's conjecture suggests that the answer is no.

An identity which involves Euler's totient function

2012-11-14T21:46:24Z

It is well known that $$ \sum_{n=1}^\infty \frac{\phi(n)x^n}{1-x^n}=\frac x{(1-x)^2}, $$ where $\phi$ is Euler's totient function and $|x|<1$ - see [Hardy and Wright, Theorem 309]. For $x=\frac12$ this immediately yields $$ \sum_{n=1}^\infty \frac{\phi(n)}{2^n-1}=2. $$ What I need for my research is the analytic value for $$ \sum_{n=1}^\infty \frac{\phi(n)}{(2^n-1)^2}. $$ Numerically it is $1.1659457\dots$, which doesn't look like something familiar to me (or to Google, for that matter).

Any ideas?

Answer by Nikita Sidorov for Logistic map periodic point

2012-11-11T02:46:17Z

Essentially you have proved that the logistic map is conjugate to the doubling map $Tx=2x\bmod 1$. Now, $T$ is in turn conjugate to the shift map $\sigma:\Sigma\to\Sigma$, where $\Sigma$ is the space of infinite 0-1 words.

More precisely, if $$ \pi(w_1,w_2,\dots)=\sum_{n=1}^\infty w_n2^{-n}, $$ then you have $$ \pi \sigma = T\pi. $$ Since $\pi$ is 1-1, except for a countable set of finite words, you can just take any word $u$ of length $m$ and the corresponding infinite word $w=uuuu\dots$. Clearly, $\sigma^m(w)=w$, i.e., $w$ is $\sigma$-periodic of period $m$. (With a little effort you can make this the smallest period.)

For instance, $w=001001001\dots$ is of period 3.

Now take $x:=\pi(w)$; it is $T$-periodic of period $m$. Finally, use you conjugate map to turn $x$ into an $m$-periodic point for the logistic map.

Answer by Nikita Sidorov for Prove log of eigenvalues are dense in R?

2012-09-20T15:15:59Z

In addition to Doug's nice answer above: it is probably even easier to show that the set of simple Parry numbers is dense in $(1,\infty)$. More precisely, let $\beta>1$ and let $(d_n)_{n=1}^\infty$ be the greedy $\beta$-expansion of 1, i.e., $$ 1=\sum_{n=1}^\infty d_n\beta^{-n}, $$ where $d_1=\lfloor \beta\rfloor, d_2=\lfloor\beta\ \text{frac}(\beta) \rfloor, d_3=\lfloor \beta\ \text{frac}(\text{frac}(\beta))\rfloor $, etc. (Here $\lfloor\cdot\rfloor$ stands for the integer part and frac$(\cdot)$ for the fractional part.)

A number $\beta$ is called a simple Parry number (also known as a simple $\beta$-number) if $(d_n(\beta))_1^\infty$ has only a finite number of nonzero terms (i.e., ends with $0^\infty$). It is known that any Parry number is a Perron number; also, it is obvious that the Parry numbers are dense, since for any $\beta$ with an infinite $(d_n(\beta))_1^\infty$ we can truncate this sequence at any term and get a $d_n(\beta')$ for some simple Parry number $\beta'$. Since $(d_n(\beta))_1^\infty$ and $d_n(\beta')_1^\infty$ are close (in the topology of coordinate-wise convergence), so are $\beta$ and $\beta'$.

For more details and some references you may read the first couple of pages of this paper, for instance.

Answer by Nikita Sidorov for Liouville's Theorem in Diophantine Approximation

2012-06-27T21:43:14Z

The constant $c=1/\sqrt5$ (with $n=2$) works for any $\alpha$. If $\alpha$ is not, roughly speaking, the golden ratio, then $c$ can be improved to $1/2\sqrt2$, etc. If one removes a certain infinite sequence of quadratic irrationals, one can take $c=1/3$, but this is the best you can do in a general setting.

A nice exposition can be found in [Cassels, An Introduction to Diophantine Approximation]. You may also start with a Wikipedia article.

Answer by Nikita Sidorov for Eigenvalues for toral Anosov automorphisms

2012-03-18T17:25:06Z

Given $k < d$, one can always construct a monic polynomial irreducible over $\mathbb Q$ with exactly $k$ roots less than 1 in modulus and $d-k$ roots greater than 1 in modulus. This follows from the general construction of algebraic units, namely, each group of units of an algebraic field contains a unit with a given $k$ -- see, e.g., [Borevich and Shafarevich].

Then you can simply take the companion matrix of such a polynomial.

Or do you need an explicit construction?

Answer by Nikita Sidorov for What is the adic realization of a Bernoulli shift ?

2012-02-16T13:18:59Z

The short answer is that nobody knows. The reason is that Vershik's proof uses Rokhlin's towers and is thus virtually non-constructive.

As far as I know, the only known examples of explicit adic realizations are substitutional dynamical systems and the irrational rotations of the circle. Even for a simple ergodic rotation of the 2-torus this is an open question, let alone Bernoulli shifts.

Large geodesically convex subsets of tori

2012-01-16T21:00:23Z

Let $X=\mathbb T^d=\mathbb R^d/\mathbb Z^d$ and let $E$ be a proper open subset of $X$. We say $E$ is geodesically convex if for any $x,y\in E$ the shortest geodesic connecting $x$ and $y$ lies in $E$.

Question. How large can the Haar/Lebesgue measure of $E$ can be?

For example, is $d=2$, then it seems that this cannot exceed $1/2$. Say, $[0,1)\times [0,s)$ is geodesically convex if and only if $s\leq1/2$. (If $s>1/2$, then $[x,x+\delta]$ is not the shortest geodesic for any $\delta\in(1/2,s)$ and any $x\in(0,1)$.)

Is it true for any $d\ge2$ that the measure of such an $E$ cannot exceed $1/2$?

Answer by Nikita Sidorov for bound for zeros of a polynomial with bounded integer coefficients

2012-01-10T11:14:50Z

Just a brief remark that if $M=2$ and the constant term is $\pm2$, then these are called Garsia numbers. It is known that $z=1$ is a limit point for this set (and some computational results as well). Perhaps, you'll find the following recent paper useful as far as the techniques are concerned.

Answer by Nikita Sidorov for How to prove the Hahn-Banach constructively

2011-09-27T21:34:22Z

The idea is to show that one can extend a linear functional from an $n$-dimensional space to a space of dimension $n+1$ without increasing its norm. See, for instance, my notes (Lemma E.2)

In fact, by doing so, you can prove THBT constructively for any separable space.

Answer by Nikita Sidorov for Other realms for studying symbolic dynamics

2011-04-30T13:19:33Z

I believe what you're referring to here are called $\mathbb Z^d$-actions (with $d=2$ in your setting). This is a pretty large area of (algebraic) dynamics with people like Klaus Schmidt, Doug Lind, Thomas Ward and Manfried Einsiedler (and many others) actively working in it.

Perhaps, the following short survey paper by Klaus Schmidt could help you get going: http://www.mathematik.uni-bielefeld.de/~rehmann/ECM/cdrom/3ecm/pdfs/pant3/schdtk.pdf

Answer by Nikita Sidorov for Kronecker Approximation theorem and Fibonacci numbers

2011-03-11T00:35:57Z

Well, as Gerry has pointed out, this is certainly not true for all $\alpha$. On the other hand, this is true for a.e. $\alpha$. More precisely, the sequence $2^n\alpha$ is equidistributed mod 1 for a.e. $\alpha$.

I believe this result is due to H. Weyl and can be found in Cornfeld, Fomin and Sinai `Ergodic Theory'. (I don't have it with me.)

The same must be true for the Fibonacci sequence, I'm sure.

So, what you probably need is for this to be true for all $\alpha$, except some small (countable?) set. After all, $\|2^n\alpha\|<\varepsilon$ is indeed much weaker than equidistibution.

Update. Come to think about it, the answer is as follows: let $$ \alpha = \sum_{k=1}^\infty a_k2^{-k} $$ be the binary expansion of $\alpha$. Then the sequence $2^n\alpha\bmod 1$ gets arbitrarily close to 0 if and only if the sequence $(a_k)$ has unbounded strings of 0s. In particular, any rational $\alpha$ is out of the picture, apart from the binary rationals, of course.

All in all, your set of $\alpha$'s is indeed of full measure, but the exceptional set is of Hausdorff dimension 1, i.e., pretty big.

For the Fibonacci sequence you'll need to replace binary expansion with the $\beta$-expansion, where $\beta=(\sqrt5-1/)2$, with the same conclusion.

Commuting matrices in GL(n,Z)

2011-02-16T14:02:14Z

Suppose $M$ is a "hyperbolic" matrix in $GL(n,\mathbb Z)$, i.e., that its characteristic polynomial $p$ is irreducible over $\mathbb Z$ and has no roots of modulus 1.

Is there a closed description of the set of elements of $GL(n,\mathbb Z)$ which commute with $M$?

I have a vague recollection that it is somewhat similar to the Dirichlet theorem on the units of an algebraic field, but it is really vague so a reference would be appreciated.

The case I'm most interested in is when $p$ has only one root of modulus greater than 1. Can $M$ commute with another matrix $M'$ with the same property (and $M, M'$ not being powers of the same matrix in $GL(n,\mathbb Z)$)?

Answer by Nikita Sidorov for Mathematical "urban legends"

2011-01-28T09:03:16Z

In a fabulous French comedy La moutarde me monte au nez Pierre Richard's character is a maths teacher at a local girls' college. One day he accidentally ends up in a mansion that belongs to an American movie star (Jane Birkin). Frighened of a potentially dangerous intruder, she sets her pet cheetah on him, and the academic promptly jumps on a huge chandelier.

To prove to her that he was indeed a maths lecturer, he had to answer a few questions. First - to expand $(ax+b)^2$ (which he did) and then - to integrate $\sin(ax+b)$ (again, success). All that - hanging from a chandelier, with a cheetah pacing below.

Only after that she allows him to climb down to the floor... and then they have a romantic dinner, needless to say.

Answer by Nikita Sidorov for The sum of integers being a bijection

2010-12-31T18:24:07Z

If you accept that 0 is not a natural number, then there is a very simple answer to your question: take $P$ to be all numbers whose expansions base 4 contain only digits 0 and 1 and $Q$ to contain only digits 0 and 2. Then $P\cap Q={0}$, which we have boldly excluded.

Also, both sets have the lowest possible asymptotic density of order $1/\sqrt n$, which is kinda nice.

Answer by Nikita Sidorov for Statistics of a simple Markov chain

2010-12-20T22:34:21Z

The measure $\mu_\lambda$ on an interval whose distribution is given by the random variable $$\sum_{n=1}^\infty \epsilon_n\lambda^n,$$ where the $\epsilon_n$ assume the values 0 and 1 (or $\pm1$) independently with probabilities $(p,1-p)$ is called a biased Bernoulli convolution.

If one assumes $\lambda\in(0,1/2)$, then $\mu_\lambda$ is supported by a Cantor set and is consequently singular. If $\lambda=1/2$, then it is a well known singular measure on $[0,1]$. (It is invariant and ergodic under the doubling map $\tau x=2x\ \bmod 1$ and so is the Lebesgue measure.)

The most interesting case is $\lambda\in(1/2,1)$. Here if $p\in[1/3,2/3]$, then for a.e. $\lambda$ the measure $\mu_\lambda$ is known to be equivalent to the Lebesgue measure. If $\lambda^{-1}$ is a Pisot number, then it is singular. (Which was essentially proved by Erdős in 1939.)This is almost all that is known about these measures.

For more detail see, e.g.,

B. Solomyak, Notes on Bernoulli convolutions

Answer by Nikita Sidorov for Never appeared forthcoming papers

2010-12-06T20:16:28Z

A. Bertrand-Mathis, Le $\theta$-shift sans peine

Answer by Nikita Sidorov for Characteristic polynomials for $K$-Bonacci numbers: what's their name?

2010-11-23T22:13:20Z

The dominant root of such a polynomial is often referred to as a multinacci number. These numbers are known to be Pisot numbers and, indeed, tend to 2.

A free subgroup of GL(2,Z)?

2010-11-21T20:21:46Z

Is the subgroup of $GL(2,\mathbb Z)$ generated by the matrices $$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \ \ \text{and} \ \ \left( \begin{array}{cc} 2 & 1 \\ 1 & 0 \end{array} \right) $$ ~~free~~ of exponential growth? More generally, how does one find all the relations between two matrices?

I am sure this is well known, so any relevant references will be appreciated.

My motivation comes from dynamical systems where these matrices specify two automorphisms of the 2-torus; I am interested in studying the orbits of their joint action.

Non-Hölder continuous devil's staircases

2010-11-06T01:51:31Z

Let $f:[0,1]\to[0,1]$ be a devil's staircase in the usual sense. (That is, $f$ is continuous, non-decreasing, $f'=0$ on a set of full Lebesgue measure.) We also require the complement to the set where $f'$ vanishes to have Hausdorff dimension zero.

Question. Is it true that $f$ is not Hölder continuous?

(This looks plausible, since $f$ has `very little room' where it can grow so it has to grow very fast - at least, at some points.)

Answer by Nikita Sidorov for Fourier dimension of the sum of sets

2010-10-30T00:28:05Z

Regarding the Hausdorff dimension of sumsets, you might want to have a look at an important paper by Peres and Shmerkin:

http://arxiv.org/abs/0705.2628

There are plenty of useful references there, too.

Answer by Nikita Sidorov for What are the zero entropy invariant measures for an Anosov geodesic flow?

2010-10-14T21:33:45Z

OK, I am sure that there must be something easier for the shifts but... In my paper with Glendinning we briefly mention a construction of a subshift on two symbols of zero topological entropy. Namely, let $\sigma$ denote the shifted Thue-Morse sequence, i.e., $$ \sigma = 1101001100101101001011001101001 \dots $$ Define $X$ to be the set of all two-sided 0-1 sequences $(x_n)$ such that $$ (x_n, x_{n+1},\dots) \prec \sigma \ \ \ \forall n\in\mathbb Z $$ and $$ (1-x_n, 1-x_{n+1},\dots) \prec \sigma \ \ \ \forall n\in\mathbb Z, $$ where $\prec$ stands for ``lexicographically smaller''. The set $X$ has zero Hausdorff dimension in the standard metric on ${0,1}^{\mathbb Z}$. In fact, the number of admissible words of length $n$ in $X$ grows approximately as $n^{\log n}$.

To endow $X$ with a shift-invariant measure, one can take the sequence of subshifts of finite type converging to $X$ (by truncating $\sigma$) and $\mu$ to be the weak limit of the corresponding measures of maximal entropy, say.

Answer by Nikita Sidorov for subtracting greatest possible prime

2010-10-10T18:08:32Z

If I understand you correctly, this is effectively the question about (greedy) systems of numeration for the natural numbers. These are well understood in the case when $A$ satisfies some recurrence relation -- like the Fibonacci sequence (Zeckendorf) or the denominators $q_n$ of the CF convergents for some irrational $\alpha$ (Ostrowski).

If $A$ grows subexponentially, this is usually not good news for the ``ergodic'' questions like this.

Answer by Nikita Sidorov for How do I explain the number e to a ten year old?

2010-10-09T14:06:19Z

When I was this age, I loved the factorials. So why not try to explain it via the Stirling formula? That $n!$ is ``rather close'' to $n^n$ but you need to adjust it a bit via division by $e^n$.

Also, if he knows logarithms, the Prime Number Theorem is a good example why $e$ is the ``correct'' base of logarithms.

Answer by Nikita Sidorov for A question regarding polynomials whose roots satisfy certain algebraic relation

2010-09-27T09:39:04Z

This is rather vague but regarding relations between roots of a polynomial you may try some of Chris Smyth's papers as a starting point. For instance, this one:

C. J. Smyth, Conjugate algebraic numbers on conics, Acta Arith. 40 (1982), 333–346.

Isodiametric hull

2010-09-17T22:55:45Z

Let A be a convex compact set in the plane (with a piecewise smooth boundary, say). We want to `inflate' it in such a way that the diameter does not increase.

More accurately, we are looking for all sets C such that

a) A is a subset of C; b) diam(A)=diam(C)

Let now B is the largest possible set C which satisfies these two properties.

By `largest' I mean either that it m(B) = max m(C), where m is the Lebesgue measure; or that B actually contains any C with these properties. Let us call B the isodiametric hull of A.

The simplest example of A is of course the square: here B is the superscribed disc, and it is the isodiametric hull of A in the strong sense.

Another example is the equilateral triangle, for which B is the Reuleaux triangle. Similarly, for any regular 2n-gon we have the disc, and for any regular (2n+1)-gon its isodiametric hull is a Reuleaux polygon.

The first non-trivial example that comes to mind is an isosceles triangle that isn't equilateral. It is clear that the hull is always a set of constant diameter but how does one actually obtain it? It seems that its boundary - a curve of constant width - is not a finite union of circular arcs.

I wonder if all this is well known (being such a natural question!). In particular, does the isodiametric hull of a set always exists in the strong sense?

Added: of course, if there is no IDH in the strong sense, B may not be unique. Its area is unique, though. How does one find it?

Answer by Nikita Sidorov for Measure 0 sets on the line with Hausdorff dimension 1

2010-08-18T19:14:03Z

It is a very common phenomenon in ergodic theory when the set of points which do not satisfy the Birkhoff ergodic theorem (i.e., a set of zero measure) has full Hausdorff dimension.

See, for instance, http://www.math.psu.edu/pesin/papers_www/birk.pdf

Comment by Nikita Sidorov

2013-02-16T22:41:09Z

No problem. Hope it'll help.

Comment by Nikita Sidorov

2013-01-18T08:59:18Z

So, in terms of continued fractions, we have $a_{n+1}=[a_{n-1}; a_{n-2},\dots, a_2, a_1, a_0, a_1]$.

Comment by Nikita Sidorov

2013-01-18T00:06:09Z

Try Binet's formula (mathworld.wolfram.com/…). Btw, I don't understand how both series can be equal to 1 when one is clearly larger? Something's not right.

Comment by Nikita Sidorov

2013-01-13T17:38:55Z

Thanks. Yes, introducing measures looks like a good approach here.

Comment by Nikita Sidorov

2013-01-13T17:37:57Z

This paper is about lacunary sets which are generalizations of self-similar sets. I am interested in perturbed self-similar sets, so I don't quite see how his result could possibly help me.

Comment by Nikita Sidorov

2013-01-08T01:19:23Z

A school teacher?

Comment by Nikita Sidorov

2012-12-30T14:47:53Z

Of course, not. The set of analytic functions is dense in $C(\Delta)$, so for any continuous non-analytic function ($f(z)=\overline z$, say) there exists a sequence of analytic functions which converges to $f$ uniformly and hence, pointwise.

Comment by Nikita Sidorov

2012-12-30T00:58:15Z

Yes, MathSciNet is less generous and indeed more accurate. However, it is too old-fashioned in the sense that it only counts published papers. So, if you upload a preprint and then it takes a few years for this paper to appear, say (which often happens given low speed of refereeing and massive backlogs in some journals), then all the citations you preprint gathers during this unfortunate limbo will be ignored by MathSciNet - but not by Google Scholar. Also, there are `borderline mathematical' or just non-mathematical journals MathSciNet doesn't list, which may affect your H-index as well.

Comment by Nikita Sidorov

2012-12-06T10:16:46Z

Margaret: Thanks. Yes, this was the reason, and Bernstein saw it mainly as a result in Probability.

Comment by Nikita Sidorov

2012-12-06T00:16:28Z

Fredrik: not really. Take, for instance, $f(x)=x^2$; then $B_n(f;x)=x^2+x(1-x)/n$, so $B_n(f;x)-f(x)\asymp 1/n$.

Comment by Nikita Sidorov

2012-12-05T23:55:53Z

Thanks! What's a Tonelli polynomial? I have to admit I've never heard of them and Google is no help either...

Comment by Nikita Sidorov

2012-11-15T12:51:03Z

Sinai - No, I haven't. I guess I'm not sure how... fedja - Thanks, but this constant is not that important. It's just a part of a technical argument, nothing more.

Comment by Nikita Sidorov

2012-11-11T13:13:42Z

Right. Note however that for this word we know for sure that it is of period $m$ and not of any $k<m$.

Comment by Nikita Sidorov

2012-11-11T12:56:53Z

The word $(10^{m-1})^\infty$ is $m$-periodic for $\sigma$, whence $x=0.5/(1-2^{-m})$ is $m$-periodic for $T$. If your formula is correct I haven't checked it), then $\sin^2(\pi/(1-2^{-m}))$ is your guy.

Comment by Nikita Sidorov

2012-11-04T15:27:10Z

What's $G_m(f,D)$?