User fedor petrov - MathOverflow

Algebraic conditions of separability

2013-05-09T09:13:48Z

Let $X$ be a real vector space (without any norm), and $Y$ be a convex subset of $X$, $0\notin Y$. The goal is to find a hyperplane $L$ passing through 0 such that $Y$ lies in a closed halfspace bounded by $L$. Under which conditions is it always possible? Usual Hahn-Banach theorem requires that $Y$ has a non-empty algebraic interior, i.e. there exists $p\in Y$ such that for any $x\in X$ the point $p+t(x-p)$ belongs to $Y$ for small enough $t>0$. But there are important cases, when the statement is still true, while algebraic interior is empty. Example: $Y$ is a cone of non-negative functions in $L^p$, shifted by any non-zero non-negative function. Are there general algebraic conditions, which cover this case and garantee the existence of separating hyperplane?

When separation in $L^1$ is possible?

2013-05-02T22:50:50Z

Let $A$, $B$ be disjoint convex closed subsets of the Banach space $L^1[0,1]$. Assume additionally that $A$ is bounded and $A$, $B$ are closed under convergence in measure. Then there exists a closed hyperplane, which strictly separates $A$ and $B$.

This follows almost immediately from the Komlós lemma (if the distance between $A$ and $B$ is positive, then usual Hahn-Banach theorem works, if not, let $a_n\in A$, $b_n\in B$ be so that $\|a_n-b_n\|\rightarrow 0$, by Komlós lemma we may without loss of generality suppose that $c_n:=(a_1+\dots+a_n)/n$, $d_n:=(b_1+\dots+b_n)/n$ converge in measure to $c\in A$, $d\in B$ respectively, but $\|c_n-d_n\|\rightarrow 0$, hence $c=d$, a contradiction.)

Two questions are:

1) This looks like a very classical subject, what is appropriate reference?

2) Are there some weaker general assumptions for the existence of separator in $L^1$ or maybe in more general spaces?

Nim game for odd number of stones

2012-11-08T09:01:13Z

Consider the classical Nim game with total number of stones being odd. Then the first players wins, of course, what follows from the general description of winning positions. But is there some shorter (independent of full theory) explanation of this fact, maybe with implicit strategy or whatever?

Answer by Fedor Petrov for Area of a lattice polygon in terms of its width

2013-04-02T02:32:26Z

$\alpha=3/8$ is sharp according to, say this article, the authors refer to [L. Fejes-Toth and E. Makai, Jr., On the thinnest non-separable lattice of convex plates, Studia Sci. Math. Hungar. 9 (1974), 191–193.]

When factors may be cancelled in homeomorphic products?

2010-05-29T21:26:09Z

It is easy to see that if $A\times B$ is homeomorphic to $A\times C$ for topological spaces $A$, $B$, $C$, then one may not conclude that $B$ and $C$ are homeomorphic (for example, take $C=B^2$, $A=B^{\infty}$). The question is: for which $A$ such conclusion is true? I saw long ago a problem that for $A=[0,1]$ it is not true, but could not solve it, and do not know, where to ask. Hence am asking here. The same question in other categories (say, metric spaces instead topological) also seems to have some sense.

Continuity of barycentre in Hausdorff metric

2012-05-07T19:07:46Z

Let $K_1$, $K_2$ be two convex compact sets in $\mathbb{R}^d$, and $p_1,p_2$ be their barycenters. Is it true that the distance between $p_1$ and $p_2$ does not exceed a Hausdorff distance between $K_1$ and $K_2$? If not, maybe there is some weaker estimate, say, uniform continuity of the map (convex body)$\rightarrow$ (its barycenter) for bodies inside, say, unit ball?

UPDATE. As Anton pointed out, the answer is obviously no, just take rectangle $\varepsilon\times 1$ and divide it by diagonal onto two triangles. Let me ask another question: is the barycentre of a closed $\varepsilon$-neighborhood close to the barycentre of initial body uniformly for all bodies inside unit ball?

Combinatorial meaning of the functional equation for logarithm

2012-11-16T13:39:43Z

If we set $\exp(x)=\sum x^k/k!$, then $\exp(x+y)=\exp(x)\cdot \exp(y)$. In terms of coefficients it means that $(x+y)^n=\sum \frac{n!}{k!(n-k)!} x^ky^{n-k}$, i.e. just binomial expansion.

Now consider logarithm. Set $L(x):=\sum_{k>0} x^k/k$, then $L(x)=-\log(1-x)$ in a sense, and hence $$L(u+v-uv)=L(u)+L(v),$$ i.e. $\sum (u+v-uv)^n/n=\sum (u^n+v^n)/n$, or, if we pass to coefficients of $x^ay^b$ ($a,b\geq 1$), we get $$ \sum_k (-1)^k\frac{(a+b-k-1)!}{(a-k)!(b-k)!k!}=0 $$

The question is what is combinatorial meaning of this identity. Maybe, it is some exclusion-inclusion formula, as it is usual for alternating sums?

T. Carleman's method on eigenvalues asymptotics

2012-11-12T18:28:42Z

What is the best available less or more modern introduction to the subject?

distribution of coprime integers

2010-04-29T07:40:52Z

Let $0 < a < 1$ be fixed, and integer $n$ tends to infinity. It is not hard to show that the number of integers $k$ coprime to $n$ such that $1\leq k\leq an$ asymtotically equals $(a+o(1))\varphi(n)$. The question is: what are the best known estimates for the remainder and where are they written?

Many thanks!

Graham-Rothschild via Hales-Jewett

2012-09-28T12:02:57Z

I am currently reading the recent preprint of Dodos, Kanellopoulos, Tyros, where the ambitiously short proof of Density Hales Jewett theorem is provided. The important ingredient is Graham-Rothschild theorem. The authors say that it follows from the HJ by some standard Ramsey arguments, but I can not find them myself, at least immediately. Is it written anywhere? Original paper of Graham and Rothschild looks too long for being used in "simple self-contained proof" of anything. Polymath's DHJ proof does not use GR at all, on first glance.

Chebyshev's approach to the distribution of primes

2010-05-29T08:38:42Z

This is motivated by a recent question by Wadim.

The negative answer should be known, since t is very natural, in this case I would be happy to see any reference.

May Pafnuty Lvovich Chebyshev's approach to distribution of primes lead to PNT itself, if we replace $\frac{(30 n)! n!}{(15 n)! (10 n)! (6 n)!}$ to other integer ratios of factorials? If not, what are the best constants in asymptotic relation $$ c_1 \frac{n}{\log n}< \pi(n)< c_2 \frac{n}{\log n} $$ which may be obtained on this way?

Answer by Fedor Petrov for How to Rigorize an inequalities argument

2012-08-30T10:29:27Z

Take, say, $a=2p^3$, $p=1/2\sqrt{n}$. Then $$(1-p)/(1-a)^n=\exp(-p+na+O(p^2+na^2))=\exp(-1/4\sqrt{n}+O(1/n)).$$ You need lower estimate of the RHS, hence upper estimate of $(1-p)/(1-a)^n$, you mau use $\exp(-1/5\sqrt{n})$ for large enough $n$. Next, use an estimate like $1-p\geq e^{-2p}$ for $0 < p < 1/100$, and for large $n$ we estimate RHS from below as $$\exp(-2\exp(-c^2k^2/5\sqrt{n})n^{ck}).$$ So, it is enough to satisfy inequality $$ 10n^{ck} < \exp(c^2k^2/5\sqrt{n}), $$ or, taking logarithm of both sides, $$ \log 10+ck\log n < c^2k^2/5\sqrt{n}. $$ This holds for $c=10$ and large enough $n$.

Answer by Fedor Petrov for Convergence rate of an iterative process

2012-08-06T14:27:03Z

The standard techniques is as follows. At first, we guess the growth rate by replacing the discrete dynamical system to ODE: $a_n-a_{n-1}=-a_{n-1}\phi(a_{n-1})$ is replaced to $A'(n)=-A(n)\phi(A(n))$, where function $A(n)$ imitates $a_n$. Nex, we solve this equation, rewriting it as $g(A(n))'=1$, where $g'(t)=-1/(t\phi(t))$. Our guess is that $g(A(n))$ behaves like $n$ (since it derivative behaves as 1), and the same for $g(a_n)$. For proving this guess rigorously we introduce a new sequence $b_n=g(a_n)$ and write down the formula $b_n-b_{n-1}=g(a_n)-g(a_{n-1})=(a_n-a_{n-1})g'(s)$ for some $s$ between $a_{n-1}$ and $a_n$. Next, $(a_n-a_{n-1})g'(s)=\frac{a_{n-1}\phi(a_{n-1})}{s\phi(s)}$. Assume that $\phi(x):\phi(y)$ tends to 1 when $x/y$ tends to 1 and $x,y$ tend to $+0$. Then we may conclude that our last fraction tends to $1$, and by usual Stolz theorem conclude that $b_n$ behaves like $n$.

Example: $\phi(x)=x$, $g(t)=1/t$, so we consider the sequence $b_n=1/a_n$. We get $b_{n}-b_{n-1}=\frac{a_{n-1}-a_{n}}{a_na_{n-1}}=\frac{a_{n-1}}{a_{n}}$, what clearly tends to 1, hence $b_n\sim n$.

Stone-Weierstrass analogue for $L^p$

2012-05-04T18:26:06Z

Let $A$ be a complex algebra of bounded measurable functions on the measure space $(X,\mu)$ (case of $[0,1]$ with Lebesgue measure is enough for me) closed under conjugation. Assume that $A$ separates points, i.e. there is no non-trivial measurable partition of $X$ such that each function in $A$ is constant on (almost every) part. Is it true that $A$ is dense in $L^p(X,\mu)$ for $1\leq p < \infty$?

Two standard probability spaces

2012-04-29T22:43:48Z

Let $(X,\cal{A},\mu)$ be a standard (Lebesgue-Rokhlin) space with complete probabilistic measure (for example, $[0,1]$). Let $\cal{B}\supset \cal{A}$ be a wider then $\cal{A}$ $\sigma$-algebra on $X$, and let $\nu$ be an extension of $\mu$ onto $\cal{B}$ so that $(X,\cal{B},\nu)$ is a standard probability space again. Then $\cal{A}=\cal{B}$. We hope that we may prove it, but this should be definitely known if true, so let me ask either for the reference or for one-sentence proof.

Answer by Fedor Petrov for Finite dimensional subspaces of $L^1.$

2012-04-20T19:12:16Z

Greg is right, of course, the dual must be a zonotope.

Let me mention also a direct characterization: for any vectors $x_1,\dots,x_k,y_1,\dots,y_m$ such that $\sum |f(x_i)|\geq \sum |f(y_j)|$ for any linear functional $f$, one may deduce that $\sum \|x_i\|\geq \sum \|y_j\|$. For Euclidean norm it is usual stuff in integral geometry: for proving inequality between sums of lengths one proves corresponding inequality for sums of projections to the same line. The norms, for which such trick is possible, are exactly those coming from sections of $L^1$.

Answer by Fedor Petrov for Equal digit sums

2012-04-19T20:20:42Z

Yes, but if we replace condition $a\ne b$ to $a/b\ne 10^k$ for all integers $k$.

Lemma: $s(9n)=9s(n)$ iff decimal digits of $n$ are only 0's and 1's. Else $s(9n)<9s(n)$.

Call two numbers equivalent, if their ratio is a power of 10 (with integer exponent).

Consider numbers 1,11,111,... Two of them are congruent modulo a, hence their diffrence 11...100..0 equals $ka$ for some natural $k$. Replace pair $(a,b)$ to $(ka,kb)$ and then replace new $a$ (old $ka$) to equivalent number of the form 11...1, totally $m$ ones. Also, divide $b$ to maximal possible power of 10.

Now $s(9a)=9s(a)$, hence the same holds for $b$, hence by lemma $b$ also has only 1's and 0's in its decimal representation and the number of ones equals $m$. In particular, $b>a$ and last digit of $b$ equals 1. Now choose $N$ such that $Nb=11\dots 1$, then $Na < Nb$ and due to $s(Na)=s(Nb)$, $Na$ has a digit different from 0 and 1. Then by lemma $s(9Na)<9s(Na)$, while $s(9Nb)=9s(Nb)$. A contradiction.

I know this as an old problem by Sergey Berlov, by the way. First time I saw it in 1997 in Sochi on the event for high school students I have participated in:)

Answer by Fedor Petrov for Coloring a unit cube

2012-04-19T21:07:08Z

I work with $I_n$ instead $I_{n+1}$. Consider pairs of opposite vertices. There are $2^n$ such pairs. We want to find $K=O(2^n/n)$ such pairs (call them nice) so that for any other pair $(u,u')$ there is a nice pair $(v,v')$ with distance $d(u,v)=1$. Then we may color all vertices in at most $2K$ colors so that each color consists either of two opposite vertices, or of one vertex and few vertices on distance $n$ from it. Indeed, enumerate all nice pairs $(u_1,u_1')$, $(u_2,u_2'),\dots$. On $k$-th step we consider the (yet uncolored) nice pair $(u_k,u_k')$ and consider all uncolored and not nice pairs on distance 1 from it. If there is at least one such pair, we use two new colors, one for $u_k$ and uncolored and not nice points close to $u_k'$ and viceversa. If there are no such pairs, use one color for $(u_k,u_k')$. Then proceed.

Now must explain how we find $K$ such pairs. Let's think about $I_n$ as about vector space $\mathbb{F}_2^n$. Consider $m$ independent linear functionals $f_1,\dots,f_m$ on $I_n$ and define as nice all points for which all of them vanish (plus all opposite points, since pairs are nice, not points). What is condition for our linear functionals under which for any $x\in I_n$ there exists $y\in I_n$ on distance at most 1 from $x$ with $f_1(y)=\dots=f_m(y)=0$? It is the following condition: for any vector $(c_1,\dots,c_m)\in \mathbb{F}_2^m$ there exists a unit basic vector $e=(0,\dots,0,1,0,\dots,0)$ with prescribed values $f_i(e)=c_i,1\leq i\leq m$. This is possible provided that $2^m\leq n$, because we may define values of functionals on basic vector as we wish, and we just need enough basic vector for all patterns $(c_1,\dots,c_m)$. So, we get exactly $2^{n-m}$ points, on which all functionals $f_1,\dots,f_m$ vanish, hence at most $2^{n+1-m}$ pairs.

Lower bounds on zeta(s+it) for fixed s

2010-05-07T16:27:30Z

This is most probably widely known and discussed here many times, so I am preliminay sorry.

Does Riemann conjecture imply some lower estimates on values, say $|\zeta(3/4+it)|$ for real $t$, when $|t|$ tends to infinity?

Are any such results known without assuming Riemann conjecture (many doubts here)?

Thanks!

Answer by Fedor Petrov for Atoms of regular Borel measure

2012-04-04T10:38:26Z

Without loss of generality your atom $A$ is compact (by inner regularity). Call a point $a\in A$ negligible if it has a neighborhood with zero measure inside $A$. Clearly the set $B$ of negligible points is open in $A$. If it is $A$ itself, then choose finite subcovering by those neighborhoods to get that measure of $A$ is zero. So, $A\setminus B=C$ is a non-empty compact set in $A$. It has either measure 0 or measure equal to $|A|$ (let $|\cdot|$ denote measure.) If $|C|=0$, then choose a neighborhood $V$ of $C$ with measure at most $|A|/2$ by outer regularity. $V\cap A$ has measure strictly less then $|A|$, hence 0, hence each point of $C$ is negligible. A contradiction. So $|C|=|A|$. Then replace $A$ for $C$ and we get an atom $C$ in each no point is negligible. It may contain only one point, else take two points $u$, $v$ and their disjoint neighborhoods. Both must have positive measure in $C$, a contradiction.

signs of eigenvalues of quadratic form

2012-03-30T21:40:12Z

Let $A=(a_{ij})_{i,j=1}^n$ be a symmetric real matrix, $M_k:=det(a_{ij})_{1\leq i,j\leq k}$ be its minors and $M_k\ne 0$ for all $k$. Then signs of eigenvalues of $A$ are equal (up to some permutation) to signs of $M_1$, $M_2/M_1$, $\dots$, $M_{n}/M_{n-1}$. It is clear by induction, for example: when we replace $n-1$ to $n$ by adding last row and last column, we either add one positive eigenvalue or add one negative (number of, say, positive eigenvalues may not decrease by variational principle). The sign may be obtained by the sign of product of all eigenvalues, which equals to $M_n$.

What I ask is the reference to this easy, but somehow useful statement. I completely agree that it is not quite of research level and so appreciate its possible closing.

General compactness criterion in functional spaces

2012-03-28T11:28:44Z

What follows is a total boundness criterion in the space $L^1(X)$, where $X$ is arbitrary space with probabilistic continuous measure (Lebesgue space). Of course, all such spaces $X$ and hence $L^1(X)$ too are isomorphic, but common criteria of (pre-)compactness use additional structure on $X$ (say, Kolmogorov-Riesz criterion deals with Lebesgue measure on $\mathbb{R}^n$ and uniform continuity of small shifts).

The set $A\subset L^1(X)$ is totally bounded if and only if

(i) for any $\varepsilon>0$ there exists $\delta>0$ such that $\int_Y |f(x)|<\varepsilon$ provided that measure of $Y\subset X$ is less then $\delta$ (uniform integrability).

(ii) (universal partition) for any $\varepsilon>0$ there exist a finite partition $X=\sqcup_{i=1}^n X_i$ with the following property: for any $f\in A$ there exists an ("exceptional") subset $Y\subset X$ of measure at most $\varepsilon$ such that $|f(x)-f(y)|\leq \varepsilon$ for all $i$ and all $x,y\in X_i\setminus Y$.

Kolmogorov-Riesz criterion less or more corresponds to partition of $\mathbb{R}^d$ onto small cubes.

The question is where I may find a reference to such or similar criterion.

Answer by Fedor Petrov for Traversing the infinite square grid

2012-02-18T01:19:09Z

[Sorry, I firstly misunderstood the question] Why not? Enumerate all squares. Assume that we have already visited some finite number of squares and are now placed in the boundary square (that is, one of its coordinates is either maximal or minimal between all visited squares). Say, in the upper square. Consider the square with minimal number, which is not visited yet. Our local goal is to visit it. For this we go to the up far-far away, then to the right, then to the down, and then to the left. So we have visited next square. Then go to the left and we are no in the leftmost square and number in it is also maximal.

I think, details are fairly simple at least in the case $a_n=n$. Indeed, if we go up by $+n$, $+(n+1)$, $+(n+2)$, \dots, $+(n+k)$ we increase y-coordinate by $n+\dots+(n+k)$. We could replace $+s$ to $-s$, then we would get $2s$ less sum. So, by choosing $k$ and $s$ (we may use not only one $s$, but say 2 or three different values of $s$, but do not choose two consecutive $s$) we may get all sufficiently large $y$-coordinates, making at most 2 or 3 down jumps. Moreover, even if $k$ is fixed we may get almost all coordinates of corresponding parity. Then we have the same freedom going to the right, then going down, and to the left. Choose parities and jumps to "opposite" directions for going to the necessary point.

For $a_n=n^2$ it should not be much harder.

How to vary a function with constraints to gradient?

2012-02-17T07:19:00Z

Assume that $u$ is a function in some domain $\Omega$ in $\mathbb{R}^d$ satisfying restrictions like $u(0)=0$ and $\nabla u\in P$ in any point, where $P$ is a given polytope (for example, constraints are $\partial u/\partial x_i\in [0,1]$ and $\sum \partial u/\partial x_i\leq 2$ or like so). We have to minimize the integral functional like $\int_{\Omega} \langle\nabla u(x),F(x)\rangle dx$ with some function $F$, which may change sign and so on. A priori minimum should be attained in an extreme point of the convex set of our admissible functions $u$. But is there any nice description of the set of extreme points? Clearly, in any inner point of $\Omega$ the gradient must lie on the boundary of $P$, because else we may vary $u$ by a small function supported in the small neighborhood of such a point. But this looks like not sufficient at all, because one equality like $\partial u/\partial x_1=0$ still leaves many degrees of freedom for possible variations, the problem is that they are no longer local.

many rational points on an algebraic curve

2012-02-10T17:01:12Z

Given polynomial $f(x,y)$ with integer coefficients, may be reducible, but without linear factors. For positive integer $n$ denote by $a_n$ the number of points $(x,y)\in \frac1n \mathbb{Z}^2$ on a curve $f(x,y)=0$. May it appear that $a_n$ tends to infinity (when $n$ increases taking all positive integer values), but is always finite? Similar question: if we consider only bounded part of our curve, say $\{ (x,y):f(x,y)=0,x^2+y^2 < R^2 \}$, and define $b_n$ as the cardinality of the intersection of this set with lattice $\frac1n \mathbb{Z}^2$, may $b_n$ tend to infinity?

Answer by Fedor Petrov for Integer points in dilations of a disk of volume one

2012-01-20T22:50:06Z

This is the answer only to 1). If $i(D,n)$ is polynomial, then from known relation $i(D,n)-n^2=o(n)$ we get $i(D,n)=n^2+C$. But $i(D,n)$ is always odd, while $n^2+C$ does change its parity. A contradiction.

Alas, such trick does not work even for disproving $i(D,Tn)=T^2n^2+C$ for given positive integer $T$ (which would imply that generating function is not rational, see comments).

Answer by Fedor Petrov for Combinatorial optimization and graph coloring

2012-01-17T09:38:23Z

Linear lower bound. For any For any 18 vertices we have a monochromatic quadrilateral by Ramsey theorem. It follows that the total number of monochromatic quadrilaterals is not less then ${n\choose 18}/{n-4\choose 14}$. Then one of triangles is contained in at least at least $4{n\choose 18}/({n-4\choose 14}\cdot {n\choose 3})=(n-3)/{18\choose 4}$ monochromatic quadrilaterals.

Answer by Fedor Petrov for How does one know the following surface contains no other lines?

2012-01-15T23:43:23Z

If line is parametrized by equations $x_i=a_it+b_is,1\leq i\leq 4$, then we see that $x_1^d$ is divisible by $x_2^{d-2}$ as polynomial in $t$ and $s$, so either $x_2=0$ and we are done, or $x_1=cx_2$ for some scalar $c$, we get $(c^d+1)x_2^2=x_3x_4$, which is possible only if $c^d+1=0$, in this case $x_3$ or $x_4$ vanishes, or if $x_3,x_4,x_2$ are proportional linear forms in $t$ and $s$, but in this case our line appears to be just a point.

Answer by Fedor Petrov for Binomial coefficient in Andrews' partition book

2011-10-19T23:13:58Z

Consider all subsets of ${1,2,\dots,A+1}$ of cardinality $A-s+1$. There are exactly $\binom{A+1}{s}$ subsets. For each such subset $x_1 < x_2 < \dots < x_{A-s+1}$ consider the element $x_{A-n+1}$. The number of subsets with fixed value $x_{A-n+1}=p:=A-n+j+1$ the number of desired subsets equals $\binom{A-n+j}{A-n}\binom{n-j}{n-s}=\binom{A-n+j}{j}\binom{n-j}{i}$. Then just sum up by all possible values of $j=x_{A-n+1}-A+n-1$.

injectivity of Fourier transform: is there algebraic proof?

2011-10-16T09:45:15Z

Let $L$ be the Banach algebra of $L^1$-functions from $\mathbb{R}$ to $\mathbb{C}$ with $L^1$-norm and convolution as algebra multiplication. Assume that we knew that the homomorphisms from $L$ to $\mathbb{C}$ are the zero map and evaluation of the Fourier transform at individual real numbers: $f \mapsto \int_{\mathbb R} f(t)e^{it\alpha}dt$ for some real $\alpha$. We may add a unit $e$ to $L$ artificially by considering the new Banach algebra $A:=L\oplus \mathbb{C}\cdot e$ with natural operations. Then the fact that any $L^1$-function whose Fourier transform is zero must be zero itself may be rephrased algebraically: the algebra $A$ is semisimple (as maximal ideals of unital Banach algebras correspond to homomorphisms to $\mathbb{C}$ by the Gelfand-Mazur theorem).

My question is whether this may be proved a priori and independently (and maybe for some wide class of commutative unital Banach algebras).

Comment by Fedor Petrov

2013-05-04T18:08:13Z

$S$ should be symmetric, I guess

Comment by Fedor Petrov

2013-05-03T22:53:36Z

$P(k)$ is maximal for $k$ around $n/2$, of course, and is concentrated therein. Specify, what exactly asymptotical question are you interested in.

Comment by Fedor Petrov

2013-05-02T22:41:54Z

Nice, this semms to be a "dual" situation (the highest bit in Nim-sum is non-zero, while in my question the minimal bit is non-zero). Maybe, there is some general bijection?

Comment by Fedor Petrov

2013-05-02T22:40:20Z

Or, that's exactly what I was searching for!

Comment by Fedor Petrov

2013-03-11T21:49:52Z

@Greg: formally it is not invertible, but it has semi-inversed, which are all equivalent. So, probably the two statements are "$\pi(x) \sim x/ \log(x)$" and "$p_n \sim n \log n$".

Comment by Fedor Petrov

2013-02-22T21:33:23Z

"The coloring result we use is indeed a special case of the Graham-Rothchild theorem. We do not say much about it in the paper, since this staff is considered to be part of the folklore. In any case,here are some references. 1) A simple and self-contained proof of the full Graham-Rothchild theorem can be found in: H. J. Promel and B. Voigt, Graham-Rothschild parameter sets, "Mathematics of Ramsey Theory", Springer-Verlag, Berlin (1990), 113-149.See in particular, Section 4, page 128. 2) Another excellent reference is: R. McCutcheon, Elemental Methods in Ergodic Ramsey Theory, Lect"

Comment by Fedor Petrov

2012-11-12T19:11:31Z

@Liviu: say, Laplace-Beltrami operator on the closed compact Riemannian manifold, or Dirichlet Laplacian in a (smooth, if required) domain.

Comment by Fedor Petrov

2012-11-08T11:58:55Z

Yes, but I do not ask for a strategy. There are many games with implicit proofs that the first player wins, but no one even knows how to win.

Comment by Fedor Petrov

2012-11-08T08:57:10Z

@Dmitri. It is, but this star does not make it C*-algebra (since $\|ff^{*}\|\ne \|f\|^2$ in general).

Comment by Fedor Petrov

2012-10-29T12:36:09Z

@Kristal, it is exactly the paper I mean. Now I asked its authors directly and got a satisfactory answer with references.

Comment by Fedor Petrov

2012-10-15T05:59:42Z

Thanks! Probably, linear algebra is used for linear algebraic version of Graham-Rothschild, while we need a combinatorial one?

Comment by Fedor Petrov

2012-09-29T08:18:49Z

It looks probable that one may assume (by applying appropriate projective transformation) that the ellipse is a circle. Then the condition that it may not be put in the triangle is $OI^2>R^2-2Rr$, where $I$, $r$ denote center, radius of the circle, $O$, $R$ of the section of ball by the plane of this circle. This may help at least in computational brute force approach.

Comment by Fedor Petrov

2012-08-06T11:56:25Z

what is $i$, $\sqrt{-1}$? Then the logarithm tends to 0 and the series converges, right?

Comment by Fedor Petrov

2012-08-06T11:53:23Z

the summation in the definition of $F_{j+1,b}^B(s)$ is over $i$, but the summands do not depend on $i$. It looks like a misprint.

Comment by Fedor Petrov

2012-05-30T10:39:19Z

It already gives much better bound then $O(\varphi(l))$, namely, $O(\tau(l))$.