Monthly Archive

You are currently browsing the monthly archive for avril 2015.

Repulsive vectors again

29/04/2015 in Uncategorized | Laisser un commentaire

Two posts in french have already appeared on this topic, showing that the maximal number of unit vectors having pairwise negative (resp. non-positive) inner products grow linearly wit the dimension of the space \mathbb{R}^n they live in. This is good fun; however, as mentioned in a comment, it becomes even better fun when one bothers asking, for \epsilon >0 how big a family of unit vectors v_1,\cdots,v_k\in \mathbb{R}^n can be if…

  1. … for all i\neq j, one requires v_i\cdot v_j<\epsilon;
  2. … for all i\neq j, one requires v_i\cdot v_j<-\epsilon;

Let’s deal with the first question. This involves the remarkable fact that on the sphere of very large dimension, almost all the area is concentrated on a small band near the equator (or any equator). This is the phenomenon called concentration of measure ; so pick a vector v_1\in\mathbb{S}^n. To continue your family, you have to pick a vector outside the spherical ball B=\{x\mid x\cdot v_1\geq\epsilon\}. So the concentration of measure implies that the forbidden area is of order C\exp(-cn\epsilon^2). When you have picked already k vectors, the forbidden area for the choice of the next one is at most kC\exp(-cn\epsilon^2) which is strictly less than 1 until k=C^{-1}\exp(cn\epsilon^2). Then not all the sphere is forbidden, so you can accommodate certainly C^{-1}\exp(cn\epsilon^2): exponentially (in the dimension) many instead of linearly.

The second one is easier. Indeed,

0\leq \lVert \sum_{i=1}^k v_i \rVert^2=k+2\sum_{i<j}v_i\cdot v_j\leq k-\epsilon k(k-1)

which implies k\leq \epsilon^{-1}+1 so we get a constant bound, certainly much lower than n+1 for large dimensions.

Some metric paradoxes

17/04/2015 in Uncategorized | Laisser un commentaire

I devised yesterday a false calculation of the area of the sphere S^2=\{(x,y,z)\mid x^2+y^2+x^2=1\}. The idea is quite natural. Decompose  the sphere in circles \{(x,y)\mid x^2+z^2=1-y^2\} of radius \sqrt{1-z^2}. Thus it seems that the area of a sphere should be 2\pi\int_{-1}^1\sqrt{1-z^2}dz. However, by the change of variable z=\sin x, we easily notice that \int_{-1}^1\sqrt{1-z^2}dz=\int_{-\pi/2}^{\pi/2}\cos^2xdx=\pi/2, so we get \pi^2, instead of 4\pi, the well known value we should find. What’s wrong?

Well why should it be true on the first place? The intuitive reason why this should be true consists in approximating our sphere by a ziggurat of cylinders, of height 1/n and radius \sqrt{1-(i/n)^2}, thus getting something like \frac{2\pi}{n}\sum_{i=-n}^{n-1}\sqrt{1-(i/n)^2} for the area of our tower. This Riemann sum does converge to 2\pi\int_{-1}^1\sqrt{1-z^2}dz, but there’s no reason why it should be the area of the sphere. There’s no reason why it should be the area of anything definite either… Notice by cutting this picture by a plane, it amounts to approximating a (quarter of a) circle by a bunch of vertical segments… whose sum of lengths is of course constantly equal to 1, instead of converging to \pi/2.

In the same vein, take a half circle based on the segment [-1,1],  and then two smaller half circles under it, and split again each arc into two arcs. This yields a sequence of curves \gamma_n :[-1,1]\rightarrow \mathbb{R}^2 which converge in the L^{\infty} norm to the straight line segment, but which have a constant length \pi which doesn’t converge to the length of the limit curve. Indeed, the length of a curve is not a continuous function, only semi-continous.

So we have to think hard about the notion of surface area of a (say convex) body in the space. Certainly the right way to proceed is via Minkowski content (in other words in this case: derivative of the volume of the sphere) or Hausdorff measure.

Zeros of polynomials modulo $latex n$ in several variables

04/04/2015 in Uncategorized | Laisser un commentaire

In the Green-Tao method appear quite often expressions such as \mathbb{E}\prod_{i}1_{d_i\mid\psi_i(n)} for some system of affine linear forms \psi_i:\mathbb{Z}^d\rightarrow\mathbb{Z} where the d_i are some positive integers. The most basic example would be \mathbb{E}_{n\leq N}1_{d\mid n}=\frac{1}{N}\lfloor \frac{N}{d}\rfloor=\frac{1}{d}+O(1/N)=\mathbb{E}_{n\in\mathbb{Z}/d\mathbb{Z}}1_{n=0}+O(1/N) where the last equality is here only to insist heavily on the form a general statement will have to take. A bit more generally, one easily sees that if f:\mathbb{Z}\rightarrow \mathbb{Z} is d-periodic, then its average until N is basically its average until d+O(d/N). Following the ideas from Green-Tao, in fact we can show that for our general problem, the asymptotic should be analogously \mathbb{E}_{n\in (\mathbb{Z}/m\mathbb{Z})^d}1_{\forall i,d_i\mid\psi_i(n)} where m is the gcd of the d’s.

Thus, applying this method, one has frequently to deal with such « local densities », the intersection of the zero sets of affine forms. More generally again, one may have to deal with things like \alpha_P(p^2):=\mathbb{P}_{n\in(\mathbb{Z}/p^2\mathbb{Z})^d}(P(n)=0) for some polynomial P\in\mathbb{Z}[X_1,\dots,X_d]. Say P=\prod_{i=1}^t\phi_i where the \phi_i are affine linear forms, so that P is of degree t. Suppose also that no two of them are affinely dependant, even when reduced modulo p. Then to compute \alpha_P(p^2), notice that in order for n to satisfy P(n)\equiv 0[p^2], either two of the forms must be divisible by p in n, or one must be divisible by p^2 there.

To analyse the first possibility, reduce the forms modulo p, so they are as seen affine forms on the field \mathbb{F}_p. They are non-zero form, so the image of each linear part is of dimension 1 and the kernels of dimension d-1; so the zero locus of each of our affine forms is a hyperplane, and the hypothesis of no affine dependance ensures that the intersection of any two of these hyperplanes is of dimension d-2. So there are only p^{d-2} common zero for each pair of forms. But each point of \mathbb{F}_p^d gives rise to p^d antecedents in (\mathbb{Z}/p^2\mathbb{Z})^d under the map of reduction modulo p. Finally, this possibility provides a summand of at most \binom{t}{2}p^{-2} to \alpha_P(p^2).

To compute now \mathbb{P}_{n\in (\mathbb{Z}/p^2\mathbb{Z})^d}(\phi_i(n)=0), notice that any such 0 must arise from a 0 mod p. Now there are p^{d-1} 0 mod p, because the set of zeros is a hyperplane. Then we can use a form of Hensel’s lemma in several variables. To obtain such a statement, we rely on the following simple identy for any Q\in\mathbb{Z}[X_1,\dots,X_d]:

Q(x+p\overrightarrow{k})\equiv Q(x)+p\,\overrightarrow{\mathrm{grad}}(Q)\cdot \overrightarrow{k}\text{ mod }p^2

which shows that if Q(x)=0\text{ mod }p, so Q(x)=mp\text{ mod }p^2 and latex \text{grad}(Q)\neq 0\text{ mod }p$ then the vector \overrightarrow{k} is constrained to live in a hyperplane if Q(x+p\overrightarrow{k}) is to vanish. So there are only p{d-1} elements y\in\mathbb{Z}/p^2\mathbb{Z} with x\equiv y [p] and Q(y) \equiv 0[p^2]. Of course if Q is affine then the gradient is simply the linear part. Thus the number of roots modulo p^2 is p^{2d-2}. By the union bound, we see that:

\mathbb{P}_{n\in (\mathbb{Z}/p^2\mathbb{Z})^d}(\exists i:\phi_i(n)=0)\leq tp^{-2}. In the end, \alpha_P(p^2)\ll_t p^{-2}.

To find more about this calculation and similar ones and the reason why I am interested in them, look at this article here.