User ilya bogdanov - MathOverflow

Answer by Ilya Bogdanov for The sum of same powers of all matrices modulo p

2013-04-07T20:32:42Z

These are just several thoughts. but it seems that they show in particular that the answr is $0$ for $k< p^p-1$.

$\def\FF{{\mathbb F}}$ 1. Firstly, denoting $d=\mathop{\rm lcm}(p-1,p^2-1,\dots,p^p-1)$ we see that $A^{pd+p}=A^p$ for every matrix $A$ (the order of a semisimple component divides $d$, and we need $p$ in order for a nilpotent component to vanish). Thus we may assume that $k < pd+p$.

2. Your sum is equal to $$ S=\sum_{a_{11}\in\FF_p} \dots\sum_{a_{pp}\in\FF_p} \left(\sum_{i=1}^p\sum_{j=1}^p a_{ij}E_{ij}\right)^k, $$ Now expand the inner brackets; we obtain $$ S=\sum_J \left(\sum_{a_{11}\in\FF_p} \dots\sum_{a_{pp}\in\FF_p} a^J\right)M_J, $$ where the outer summation is taken over some multiindices $J$ with $|J|=k$, and $M_J$ are some matrices. The summation in brackets over $a_{ij}$ gives zero unless the exponent of $a_{ij}$ is nonzero and divisible by $p-1$. Thus the sum in the brackets vanishes unless all the coordinates of $J$ are nonzero and divisible by $p-1$. So, if $k < p^2(p-1)$ then $S=0$, as is in the case $k=80$ and $p=17$.

3. For the remaining case, we need to calculate $M_J$. Assume that $J=(j_{11},\dots,j_{pp})$ (all $j$'s are multiples of $p-1$). Consider a digraph $G_J$ with $\FF_p$ as the set of vertices and $j_{k\ell}$ edges from $k$ to $\ell$. Now, if $M_J=[m_{k\ell}]$ then $m_{kk}$ is the number of Eulerian paths starting at $k$ (multiplies by the sum in brackets which is $-1$), and all other entries are zeroes.

Now let us show that the number of such cycles is divisible by $p$. We will assume that $k=1$, so that the cycles start and end at $1$. Split each cycle into subcycles starting at $1$, ending at $1$ and not passing through $1$ any more. Correspond to each cycle all the cycles obtained by permutatons of subcycles; thus the set of all cycles is partitioned into such equivalence classes, and the number of elements in each class is a corresponding multinomial coefficient $\binom{s}{s_1,\dots,s_t}$ where $s_1,\dots,s_t$ are the numbers of occurences of different subcycles. This coefficient is divisible by $p$ unless in the $p$-adic notation there are no transitions in the addition $s_1+\dots+s_t=k$.

Notice that there are at least $p$ distinct subcycles --- at least one starting from each of the edges $1\to 1$, $1\to 2$, \dots, $1\to p$. Moreover, we may partition all the subcycles into such classes --- the number in each will be divisible by $p-1$. THus, we have $p$ nonzero numbers divisble by $p-1$, and there shpuld be no transitions in addition of these $p$ numbers; this may happen only if $k\geq (p-1)+p(p-1)+\dots+p^{p-1}(p-1)=p^p-1$. So, for $k< p^p-1$ we definitely have $S=0$.

EDIT. Below in the comments, several improvements of this bound are shown.

Answer by Ilya Bogdanov for Increasing sequence of normal magic squares

2013-04-05T11:36:31Z

Here you are: $$ \begin{array}{|c|c|c|c|c|} \hline 8& 15& 21& 2& 14\cr \hline 20& 7& 13& 19& 1\cr \hline 12& 24& 0& 6& 18\cr \hline 4& 11& 17& 23& 5\cr \hline 16& 3& 9& 10& 22 \cr \hline \end{array} $$

In fact, you may start with any weakly magic square (that is --- with no conditions on the diagonals); then you just need to permute rows and/or columns to satisfy the conditions on the diagonals.

I took a standard algorithm of constructing the magic squares of odd order; amazingly, I needed only to permute the columns. It seems that a similar method should work for higher orders as well.

Answer by Ilya Bogdanov for Lattice basis with Gram-Schmidt vectors of increasing length

2013-04-03T07:44:46Z

$\def\b{{\bf b}}$ No, not any lattice has such a basis.

Notice that $||\b_n^\dagger||$ is the distance from $\b_n$ to the hyperplane $H_{n-1}=\langle \b_1,\dots,\b_{n-1}\rangle $; thus it is not greater than the minimal length of a lattice vector outside $H_{n-1}$. Moreover, they can be equal only in the case when this shortest vector is orthogonal to $H_{n-1}$.

Now, take a lattice spanned by the equilateral triangle with unit side length in the plane. Then $||{\bf b}_1||\geq 1$, and $||{\bf b}_2^\dagger||\leq 1$; the equality in the second case is achieved only if $H_1$ is orthogonal to some unit lattice vector; but then $||{\bf b}_1||=\sqrt3$. So in any case $||{\bf b}_1^\dagger||>||{\bf b}_2^\dagger||$.

More generally, we see that a lattice $\Lambda$ admits such a basis if it has some "layered" structure: the distance between two neighboring lattice hyperplanes parallel to $H_{n-1}$ is at least the smallest length of a lattice vector in $H_{n-1}$, and the same condition inductively holds for $\Lambda\cap H_{n-1}$. But even this condition seems to be quite weak.

Answer by Ilya Bogdanov for On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients

2013-02-13T11:42:42Z

$$ g(x)h(x)=(x^2-4x+5)(x^{14}+5x^{13}+16x^{12}+40x^{11}+81x^{10}+125x^9+96x^8 $$ $$ \qquad -x^7+6x^5+25x^4+71x^3+160x^2+286x+355) $$ $$ =x^{16}+x^{!5}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+240x^9+484x^8 $$ $$ + x^7 + x^6 + x^5 + x^4 + x^3 + 11x^2 + 10x + 1775. $$ $g(2)=1$, $h(2)=378919$.

In fact, it is known that each polynomial with no nonnegative real roots has a multiple with only positive coefficients. Moreover, there exists a large variety of such polynomials, hence there is nothing special in such an example.

So, having obtained $h(x)$ such that the last few coefficients of $g(x)h(x)$ are large enough, you may change few its last coefficients to make $h(a)$ prime. That's how this concrete example was obtained: first, I have found one by one the coefficients of $h(x)$ so that the first coefficients of the product are ones and the next two are positive, then I have added the negative coefficient and repeated the procedure, and then I have changes the last coefficient to make $h(2)$ prime.

It might be helpful to notice the following fact. If $g(x)$ has a complex root with argument $\alpha$, then each its multiple $p(x)$ with nonnegative coefficients has the degree at least $\pi/\alpha$. To see this, just substitute that root into $p(x)$ and look at the sign of the imaginary part.

EDIT, I'm a bit lazy to construct an explicit example with the last coefficients $\pm1$, sorry; but here is the way.

Take $g(x)=x^2(x-2)^2+1$. In the same way you may find the polynomial $h(x)$ such that $g(x)h(x)$ has positive coefficients (and $h(x)$ does not) --- since $g(x)$ has no nonnegative real roots. Next, consider $g_1(x)=x^4g(1/x)$ and construct the corresponding polynomial $h_1(x)$, say of degree $n$ (we need $h_1$ to have $1$ as the leading coefficient; it is surely possible).

It remains to notice that $g(x)(x^{n+5}h(x)+x^nh_1(1/x))$ is almost the desired example; you just need to change the appropriate coefficients of $h$ and $h_1$ to make the corresponding value prime. I am almost sure thath this is possible...

Notice that one may even decrease the exponent $n+5$ (the only fact to check is that the second factor should have a negative coefficient, and that of $h(x)$ is somewhere in the middle).

Answer by Ilya Bogdanov for What is the most extreme set 4 or 5 nontransitive n-sided dice?

2013-01-25T20:12:04Z

If you fix only the number of dice, but let the number of faces be arbitrary (or if you simply find a way to make arbitrary probabitities for different faces), then the answer for $n$ faces is $\displaystyle 1-\frac1{4\cos^2(\pi/(n+2))}$. This is proved (that's quite immodest, I know...) in my paper "intransitive roulettes" in Matematicheskoe prosveschenie, III series, 2010, Vol, 14, pp.~240--2556 but only in Russian, sorry. Similar results (lacking, perhaps, only the explicit constants) you may find in the following papers:

S. Trybula, On the paradox of $n$ random variables, Zastos. Mat. (Appl. Math.) 8 (1965), 143--154.

Z. Usiskin, Max--min probabilities in the voting paradox, Ann. Math. Statist. 35 (1964), 857--862.

The optimal example is the following. Let $q=\frac1{4\cos^2(\pi/(n+2))}$. Define $r_n=0$, $r_{i}=q/(1-r_{i+1})$. Then one can show that $1-q=r_1>r_2>\dots>r_n=0$. Now let us make the following "dice": $i$th die ($1\leq i\leq n$) makes $i$ with probability $1-r_i$ and makes $i+n$ with probability $r_i$. Then each die wins the (cyclically) previous one with probability $1-q$.

Consequently, $2/3$ is the optimal number for $n=4$ for any number of faces. Pitifully, the answers for $n>4$ are irrational, hence they are not achievable on regular dice.

It seems that the optimal configuration for $n>4$ on regular dice can be made by the corresponding modification of the general optimal example. E.g., for $n=5$ we have $r_4=q=0.30797\dots$, $r_3=0.445\dots$, $r_2=1-r_3$, $r_1=1-r_4$, so we cannot achieve 70%. On the other hand, these values can be approximated to make the following 5 icosahedral dice: $$(6\times 1, 14\times 6), \quad (9\times 2, 11\times 7), \quad (11\times 3, 9\times 8), \quad (14\times 4, 6\times 9), \quad (20\times 5), $$ where each wins the (cyclically) next one with probability at most $\frac{9\times 14}{20^2}=0.315$.

Next, there is a bound for the answer when the number of faces is bounded (or fixed, as in our case). If the number of faces is $2k$ for each die, then consider the $k$th maximal numbers on each die. Consider the die which contains the maximal number among them; then it wins the next one with the probability at least $\frac{k+1}{4k}$. Hence for the icosahedral dice the result cannot exceed $\frac{29}{40}=0.725$. THis can be achieved on the following set: $$ (5\times 1,15\times 11), \quad (7\times 2,13\times 12), \quad (8\times 3,12\times 13), \quad (9\times 4,11\times 14), \quad (10\times 5,10\times 15), $$ $$ (11\times 6,9\times 16), \quad (12\times 7,8\times 17), \quad (13\times 8,7\times 18), \quad (15\times 9,5\times 19), \quad (20\times 10), $$ but not on a smaller one. Some less optimal answers with smaller number of dice are $$ (5\times 1,15\times 9), \quad (7\times 2,13\times 10), \quad (9\times 3,11\times 11), \quad (10\times 4,10\times 12), $$ $$ (11\times 5,9\times 13), \quad (13\times 6,7\times 14), \quad (15\times 7,5\times 15), \quad (20\times 8) $$ with losing probability at most $\frac{13\times 9}{20^2}=0.2925$, and $$ (5\times 1,15\times 7), \quad (8\times 2,12\times 8), \quad (10\times 3,10\times 9), (12\times 4,8\times 10), \quad (15\times 5,5\times 11), \quad (20\times 6) $$ with losing probability at most $\frac{15\times 8}{20^2}=\frac{12\times 10}{20^2}=0.3$ --- exactly 30% on 6 dice.

Finally, for dodecahedral dice the bound is $\frac{17}{24}=0.7083\dots$, hence it is also possible to make it more than 70% (but this is impossible for octahedral dice...). The example is as follows: $$ (3\times 1,9\times 9), \quad (4\times 2,8\times 10), \quad (5\times 3,8\times 11), \quad (6\times 4,8\times 12), $$ $$ (7\times 5,8\times 13), \quad (8\times 6,8\times 14), \quad (9\times 7,8\times 15), \quad (12\times 8). $$

I cannot claim that the numbers of dice presented above are optimal for these probabilities, but it seems so.

Answer by Ilya Bogdanov for A quantitative version of Straszewicz's theorem?

2013-01-25T17:45:01Z

$\let\eps\epsilon$ $\def\conv{\mathop{\rm conv}}$ A set is called $R$-strictly convex if it is an intersection of balls of radius $R$. Denote by ${\mathop{\rm conv}}_R C$ the $R$-strict convex hull of $C$, that is --- the intersection of all balls with radius $R$ that contain $C$ (we assume that the diameter of $C$ does not exceed $R$).

The result you need is a consequence of the following

Lemma. Let $B$ be a convex compact set of diameter $\leq D$ an Euclidean space. Then for all sufficiently large $r$ the Hausdorff distance between $B$ and ${\mathop{\rm conv}}_r B$ does not exceed $A/r$, where $A$ depends only on $D$ (it even does not depend on the dimension!).

1. Let us show that the Lemma implies the statement under the question. Consider $r$ which is a bit smaller than $\eps^{-1}$ and let $B_\eps=\conv_rC_\eps$. We claim that $C\subseteq B_\eps$ (hence by Lemma the distance between $C_\eps$ and $C$ is at most $A/r$).

Actually, assume that $C\not\subseteq B_\eps$. Then $\conv_r C\neq B_\eps$, which means that $\partial \conv_r C$ contains some point $c\in C$ which is not in $B_\eps$. This point lies on the boundary of some ball of radius $r$ containing $C$; if we scale this ball at $c$ so that its raduius reaches $\eps^{-1}$ we will see that $c$ is an $\eps$-exposed point; this contradicts to the definition of $B_\eps$.

2. It remains to prove the Lemma. In fact, we show that if $d(x,B)>r-\sqrt{r^2-D^2}=D^2/2r+o(1/r)$ then $x\notin \conv_r B$. Consider the point $y\in B$ such that $d(x,B)=\|x-y\|$, and take the hyperplane $p$ passing through $y$ and perpendicular to $x-y$. Then $p$ is a supporting hyperplane for $B$; that means that $B$ is contained in the intersection of the halfspace $P$ bounded by $p$ and the ball $K$ with center $y$ and radius $D$. Now take the ball $L$ of radius $r$ whose center $o$ lies on the line defined by $x,y$ inside $P$, and whose boundary contains $\partial K\cap p$. Then $L\supset K\cap P\supset B$. On the other hand, $\|o-y\|=\sqrt{r^2-D^2}$, hence $\|o-x\|>r$, and $x\notin L$. Thus $x\notin \conv_r B$, as desired.

Answer by Ilya Bogdanov for Covering of a partial order by upwards convex sets

2013-01-04T11:23:07Z

The answer to (1) is $2^{n-1}$. If $P$ is the collection of all subsets of even cardinality, then each convex subset of $P$ is a singleton. Hence $k\geq 2^{n-1}$.

On the other hand, one can fix $a\in M$ divide all the subsets into pairs differing only in $a$. Then $P$ is the union of its intersections with the pairs, and each intersection is clearly convex.

Answer by Ilya Bogdanov for Number of matrices of a given rank satisfying this condition

2012-12-18T09:44:12Z

$\def\rk{\mathop{\rm rank}}\def\ZZ{{\mathbb Z}}$ We need to estimate the number of expansions of the form $A:=A_1-A_2=C_1-C_2$ with $\rk C_i\leq n-k$ (then $B=A_1-C_1=A_2-C_2$). Since the multiplication by a non-degenerate matrix does not change anything, this depends only on $\rk A$.

Assume, for instance, that $A$ is non-degenerate. Fix two $(n-k)$-dimensional subspaces $V_1,V_2$ of the space of rows $V=\ZZ_p^n$ with $\dim V_i=n-k$; counting the bases, we obtain that there are there are $$ N=\displaystyle \frac{(p^n-1)(p^n-p)\dots (p^n-p^{n-1})} {(p^{n-2k}-1)(p^{n-2k}-p)\dots(p^{n-2k}-p^{n-2k-1})\cdot \bigl((p^{n-k}-p^{n-2k})(p^{n-k}-p^{n-2k+1})\dots(p^{n-k}-p^{n-k-1})\bigr)^2} $$ such pairs of subspaces.

Denote by $C_i^j$ the $j$th row of $C_i$. Now let us count all the pairs $(C_1,C_2)$ such that $\mathop{\rm span} (C_i^1,\dots,C_i^n)\subseteq V_i$. Let $V'=V_1\cap V_2$. Then $C_i^j\mod V'$ is determined uniquely, hence we have $p^{n-2k}$ variants for each $C_1^j$, and $C_2$ is reconstructed from $C_1$. Thus we have $p^{n(n-2k)}$ pairs.

In total, we get $N\cdot p^{n(n-2k)}$ pairs. In fact, this is an upper bound, since the rank of $C_i$ may be less than $p-k$, and in this case one pair will correspond to several pairs $(V_1,V_2)$.

You may easily obtain a bound for $N$, but it would be better to know the relation between $p$ and $n$...

If $A$ is degenerate, then this bound should increase, since we just need $V_1+V_2$ to contain the space generated by the rows of $A$. On the other hand, we may restrict ourselves to the case when $(V_1+V_2)\mod V'=\mathop{\rm span}(A^1,\dots,A^n)\mod V'$.

Answer by Ilya Bogdanov for Sum of commuting semisimple operators

2012-12-03T16:30:53Z

The answer is still No, but for not that obvious reason. To show that, let us start with a positive claim.

1. FIrst of all, an operator $T$ is semisimple iff all the factors in the prime expansion of its minimal annihilating polynomial $\mu$ are distinct. Actually, the algebra $K[T]$ is isomorphic to $K[X]/(\mu)$; so, if there are no multiple factors, then this algebra is a direct sum of fields, and each its finitely generated module is semisimple. Otherwise, if $\mu=p^2q$ with $p$ nonconstant, then the annihilator space of $p(T)$ has no complement.

2. Now assume that the extension of $K$ generated by all the roots of characteristic polynomials of $T_1$ and $T_2$ is separable. Then they should be diagonalizable over this extension by the reasons of the minimal polynomial. Since they commute, they are simultaneously diagonalizable. Hence their sum and product are also diagonalizable, and their minimal polynomials have no multiple roots (from separability!) and hence no multiple factors. So $T_1+T_2$ and $T_1T_2$ are both semisimple.

3. And here is a counterexample for non-separable case. Let $K=F_2(t)$ be the field of rational fractions over $F_2$. Set $T_1=\begin{pmatrix}0&0&1&0\cr 0&0&0&1\cr t&0&0&0\cr 0&t&0&0\end{pmatrix}$ and $T_2=\begin{pmatrix}0&1&0&0\cr t&0&0&0\cr 0&0&0&1\cr 0&0&t&0\end{pmatrix}$; their common minimal polynomial is $X^2-t$, so they are semisimple (this polynomial is irreducible although not separable). But their sum is $S=T_1+T_2=\begin{pmatrix}0&1&1&0\cr t&0&0&1\cr t&0&0&1\cr 0&t&t&0\end{pmatrix}$ with $S^2=0$, and their product is $P=T_1T_2=T_2T_1=\begin{pmatrix}0&0&0&1\cr 0&0&t&0\cr 0&t&0&0\cr t^2&0&0&0\end{pmatrix}$ with the minimal polynomial $(X+t)^2$. Hence both are not semisimple. One may present a direct example of a spaces that cannot be complemented as $\langle e_2+e_3,e_1+te_4\rangle$ in both cases.

In fact, this example was obtained from the action of algebra $K[X,Y]/(X^2-t,Y^2-t)$ on its regular module; $T_1$ and $T_2$ correspond to $X$ and $Y$, respectively.

Answer by Ilya Bogdanov for How to divide a n dimensional simplex in n+1 equal parts

2012-11-23T08:24:29Z

In fact, there are much more such divisions. The group of simplex is $S_{n+1}$, so it contains a subgroup $H=\langle (123\dots n+1)\rangle$ of order $n+1$ acting transitively on the hyperfaces. Now take a ray $r$ from the center $O$ of the simplex, and let $\{r_1,\dots,r_{n+1}\}$ be its orbit under the action of $H$. Every $n$ of these rays generate a polyhedral cone, the union of these cones is the whole space (unless something degenerates), and $H$ permutes these cones transitively. Hence $H$ also permutes the intersections of these cones with the simplex, and they are congruent. So, we obtain a desired division.

The pictures below show two types of such divsion of a regular tetrahedron.

Answer by Ilya Bogdanov for The powers of non-empty subset of a group that generate a subgroup

2012-10-14T20:39:55Z

Consider the sets $X, X^2, \dots$. We claim that $|X^i|\leq |X^{i+1}|$, and, moreover, if $|X^i|=|X^{i+1}|$ then $|X^{i+1}|=|X^{i+2}|$. Actually, under the mapping $X^i\times X\to X^{i+1}$, $(b,x)\mapsto bx$, the preimage of any element of $X^{i+1}$ has the cardinality at most $|X|$ since all $x$-coordinates in this preimage should be distinct. Thus, $|X^i|\cdot |X|\leq |X^{i+1}|\cdot |X|$; hence $|X^i|\leq |X^{i+1}|$, and $|X^{i+1}|=|X^i|$ iff this cardinality is always $|X|$, that is -- iff $bxy^{-1}\in X^i$ for all $b\in X^i$ and $x,y\in X$. This obviously implies $cxy^{-1}\in X^{i+1}$ for all $c\in X^{i+1}$ and $x,y\in X$, and, conversely, this means that $|X^{i+1}|=|X^{i+2}|$.

Now, if $|X^n|=n$ then $X^n=G$, and the claim is trivial. Otherwise, $|X^i|=|X^{i+1}|$ for some $i\leq n-1$, and hence $|X^i|=|X^{i+1}|=\dots=|X^n|=\dots=|X^{2n}|$. Since $X^n\subseteq X^{2n}$, the latter implies that $X^n$ is a subgroup.

NB. Some background is left aside this proof. Let $H=\langle X^n\rangle$, $K=\langle X\rangle$. Since $X^{-1}\subseteq X^{n-1}$, we have $H\triangleleft K$; moreover, $XX^{-1}\subset H$, so $X$ lies in one coset modulo $H$. Hence $K/H$ is cyclic, and $X^i$ also lies in one coset modulo $H$.

Now the arguments above show that $|X^i|=|X^{i+1}|$ iff $X^i$ is a coset modulo $H$. Hence, if $k$ is the least multiple of $|K/H|$ which is not less than $|H|$, then even $X^k=H$.

Answer by Ilya Bogdanov for maximal order of elements in GL(n,p)

2012-10-12T20:13:53Z

Well, by Hamilton--Cayley, each matrix $A\in {\rm GL}(n,p)$ generates an at most $n$-dimensional subalgebra ${\mathbb F}_p[A]\subseteq M(n,p)$ thus containing at most $p^n-1$ nonzero elements. Hence the order of $A$ cannot exceed $p^n-1$.

On the other hand, consider a degree $n$ monic polynomial $P_n$ whose root is a generator $\xi$ of ${\mathbb F}_{p^n}^*$. Then a matrix with $P_n$ as its characteristic polynomial has order at least $p^n-1$ since $\xi$ is its eigenvalue.

ADDENDUM. if you wish the order to be the power of $p$, then the answer is $d=p^{\lceil \log_p n\rceil}$. Since the order of $A$ is divisible by the multiplicative orders of its eigenvalues, all the eigenvalues should be $1$. Hence the characteristic polynomial is $(x-1)^n$, so $A^d-I=(A-I)^d=0$.

On the other hand, if $A=I+J$ is the Jordan cell of size $n$ (with eigenvalue 1), then $A^{d/p}=I^{d/p}+J^{d/p}\neq I$, but $A^d=I+J^d=I$.

NB. The subgroup of all (upper-)unitriangular matrices is a Sylow $p$-subgroup in ${\rm GL}(n,p)$. So you may concentrate on it when looking at the elements of this kind.

Answer by Ilya Bogdanov for Integer solutions of x^n + y^n = z^{n-1}

2012-10-08T10:01:15Z

Take any $a,b$ and set $c=a^n+b^n$. Then the triple $(ac^{n-2},bc^{n-2},c^{n-1})$ is a solution of your equation.

Conversely, if $(x,y,z)$ is a solution and $d$ is their gcd, so $(x,y,z)=(ad,bd,cd)$, then you get $d(a^n+b^n)=c^{n-1}$. One of the solutions is presented above (with $d=c^{n-2}$). But there also exist smaller solutions --- they appear as soon as $a^n+b^n$ is not square-free.

Answer by Ilya Bogdanov for Hypergraph coloring

2012-10-03T17:16:21Z

As far as I understand, your hyperedges are of the form $\{v+c,v+d,v+e\}$ for all suitable $v$. Hence you can just color the vertices from the left to the right. Color the vertices $u\leq e-c-1$ as you wish; then, when you consider some further vertex $u\geq e-c$, there is exactly one edge with the maximal element $u$; so you can color $u$ so that this edge is multichromatic. Proceeding in this way, you will finish with no troubles; each edge was considered on some step, so it is not monochromatic.

Surely this works for any bound instead of $2e-1$.

EDIT. Even simpler: just erase $v+d$ from each edge $\{v+c,v+d,v+e\}$. The remaining graph is obviously bipartite.

Answer by Ilya Bogdanov for Property of cube hypergraph Q(n,n)

2012-10-03T13:43:11Z

1. First of all, you can ``shake down'' all your edges along each direction. That is --- choose any direction (say, vertical) and consider all the edges in $S$ of all other directions. Then simultaneously drop all of them as low as possible (preserving the condition that they are distinct). It is easy to see that on each vertical segment, the number of covered points does not increase (in fact, it becomes equal to a maximal number of parallel non-vertical edges intersecting this segment, if this segment itself was not in $S$). So, $|U|$ does not increase as well.

2. Thus, we may suppose that our set $S$ is shaken down in all directions. Now we can prove your claim by the induction on $d$. We may assume that the base of all logarithms is $n$, hence the inequality looks like $n|S|\leq |U|\log |U|$.

For $d=0$, the claim is obvious. Now assume that $d>0$, and again some of the axes is vertical. Divide all the edges in $S$ into parts $S_0,\dots,S_n$ as follows: for $i\leq n-1$, $S_i$ is the set of all non-vertical segments in $S$ having $i$ as their vertical coordinate, and $S_n$ is the set of all vertical segments. Next, let $U=U_0\sqcup \dots\sqcup U_{n-1}$, where $U_i$ is the set of all points in $U$ with $i$ as their vertical coordinate. Denote $|U|=u$, $|U_i|=u_i$. Due to the shattering, we have $u_1\geq \dots\geq u_n$.

By the induction hypothesis, we have $n|S_i|\leq u_i\log u_i$ for $i0$; next, $|S_n|\leq u_{n-1}$.

Case 1. Assume that $u_{n-1}=0$, and let $k\leq n-2$ be the maximal index such that $u_k\geq 1$. Then $$ n|S|=\sum_{i=0}^{k}n|S_i|\leq \sum_{i=0}^{k}u_i\log u_i \leq u\log u, $$ with the equality achieved only if $k=1$.

Case 2. Assume that $u_{n-1}>0$. Then $$ n|S|=\sum_{i=0}^{n-1}n|S_i|\leq \sum_{i=0}^{n-1}u_i\log u_i+nu_{n-1}. $$ So we are left to prove that $$ nu_{n-1}+\sum_i u_i\log u_i\leq u\log u. \qquad\qquad (*) $$ This happens to be a bit messy. Let us fix $u=\sum u_i$ and change the values of $u_i$'s. Since the function $x\log x$ is convex on $[1,+\infty)$, we may simultaneously change $u_i\to u_n$ for $i>0$, $u_0\to u-(n-1)u_{n-1}$, increasing the left-hand part of $(*)$. Hence, denoting $x=u_{n-1}$, $y=u_0$, we need to prove that $$ nx+(n-1)x\log x+y\log y\leq ((n-1)x+y)\log((n-1)x+y), $$ or $$ nx\leq (n-1)x\log\left(n-1+\frac yx\right)+y\log\left(1+\frac{(n-1)x}y\right), $$ or, denoting $1+c=y/x$ and dividing by $x$, $$ n\leq (n-1)\log(n+c)+(1+c)\log(n+c)-(1+c)\log(1+c). $$ In other words, we need $$ n\log n-1\log 1\leq (n+c)\log(n+c)-(1+c)\log(1+c), $$ which follows again from the convexity of $x\log x$.

Perhaps, the last part can be simplified...

Answer by Ilya Bogdanov for Three half circles on the plane may not meet nicely

2012-09-26T17:03:28Z

1. This is the answer under the assumption that the condition 2. means exactly what it says.

Consider a regular triangle with side $2+\varepsilon$ and three diameters in the middles of its sides. If you construct the half-circles towards the triangle on these diameters, you obtain the desired example.

Now about the four copies.

Lemma. Assume that the two copies of $H$ meet nicely. Consider their supporting half-planes determined by the diameters. Then their intersection is an acute angle, and the centers belong to its sides. (Possibly this angle is degenerate; in this case, it should be 0 but not $\pi$, which means that the intersection should be a strip but not a half-plane.)

Proof. If the two diameters do not intersect, then each of three pairs of the form (diameter, half-circle) and (half-circle,half-circle) meet at two points. Now, consider a point $A$ of intersection of thelines supporting the diameters. At least one diameter (say, $d_1$) does not contain $A$. Hence, if the angle in the Lemma statement is not acute, then the half-circle on $d_1$ cannot intersect $d_2$. Next, the center $C_1$ clearly lies on the side of this angle. Finally, the projection of $O_2$ onto $d_1$ should lie on the segment $d_1$, hence $O_2$ is also on the side of the angle (but not on its prolongation).

Finally, assume that the diameters intersect.Then each half-circle can intersect the other diameter in at most one more point, and the total number of the intersection points is less than 6. Lemma is proved.

Now we can prove that the four copies of $H$ cannot pairwise meet nicely. Let $c_{ij}$ be the angle from the lemma for $H_i$ and $H_j$. It is easy to see that $c_{12}$, $c_{13}$, $c_{23}$ should form an acute-angled triangle with the centers $C_1$, $C_2$, $C_3$ on its sides (just try to add the third diameter to $c_{12}$!). But then it is impossible to add the fourth half-plane --- these four half-planes should now form a quadrilateral with four acute angles!

2. Now let us assume that you speak on the half-disks. Then the answer is positive. From the previous paragraph, we see that the three diameters lie inside the three sides of some acute triangle $XYZ$, respectively.

Now consider the three distances between the centers. If all three are less than $\sqrt3$, then by Jung's theorem they may be covered by the unit disk, and the center of this disk belongs to all three half-disks.

Otherwise, assume that $C_1C_2\geq \sqrt3$, where $C_1$ and $C_2$ be the centers on the sides $XY$ and $XZ$, respectively. We have $d(C_1,XZ)\leq 1$, otherwise the respective half-circle and segment do not intersect. But then the projection of $C_1$ onto $XZ$ is at least $\sqrt2$ away from $C_2$, hence the first half-circle cannot intersect the second diameter twice. So in this case we also get a contradiction.

I may expand any part of the above sketch.

Answer by Ilya Bogdanov for Popular elements in cross-intersecting families

2012-09-07T06:24:50Z

The answer is NO without any of the two additional assumptions.

Consider a set of $(t-1)^2$ elements $A=\{a_{ij}\}_{i,j=1}^{t-1}\subset[n]$. Let each $T_k$ contain a "row" $R_i=\{a_{ij}\}_{j=1}^{t-1}$ and one additional element outside $A$, each row being assigned to almost the same number of $T_k$'s. Include also the sets $R_i$ into the family $\cal T$. Now let $$ {\cal S}=\bigl\{\{a_{1,i_1},\dots,a_{t,i_t}\} \;:\; i_1,\dots,i_t\in[t]\bigr\}. $$ Then these families are cross-intersecting. Next, $|{\cal T}|\leq n$, $|{\cal S}|=t^t$, and the maximal popularity is about $1/(t-1)$. Moreover, the second condition is satisfied: if $U$ does not contain any of $R_i$'s then $[n]\setminus U$ contains some element of $\cal S$.

In this example, $|{\cal S}|=t^t=n^{\log\log n}$ which is a bit larger than a polynomial. But in fact, if we omit the second assumption, then it suffices to take only $t$ sets into $\cal S$, namely the columns $C_j=\{a_{ij}\}_{i=1}^{t-1}$ (and remove $R_i$'s from $\cal T$ --- they are no more needed). Here the first additional assumption holds, but not the second one.

THis also shows that there is no hope for $O(1)$; namely, in the example above you may decrease $t$ a bit so that $t^t\leq poly(n)$.

PS. You may find useful to look at this paper by Zs. Tuza, especially its second section. For instance, one may derive from it the following.

If the sets $T_i$'s are independent with respect to the inclusion, then $|\cup {\cal T}|\leq \binom{2t}t$.

Answer by Ilya Bogdanov for Is this stronger Knaster-Kuratowski-Mazurkiewicz Lemma true?

2012-08-25T20:10:54Z

$\def\conv{\mathop{\rm conv}}\def\aff{\mathop{\rm aff}}\let\eps\varepsilon$It seems that you may set $n=k+t$. Consider the sets $C_1,\dots,C_t$. If they have a nonempty intersection, we are done. Otherwise, by KKM they do not cover $S_t=\conv\{e_i\colon i\in[t]\}$. Take a point $s\in S_t$ which is not covered. Since $C=\cup C_i$ is closed, its complement is open, hence some neighborhood $U(s)$ does not intersect $C$.

Now choose $\eps>0$ and define $s_i=s+\eps(e_i-s)$ for $i=t+1,\dots,n$; we have $s_i\in U(s)$ if $\eps$ is small enough. Then the subspace $V=\aff\{s_i\colon t< i\leq n+1\}$ is parallel to $\aff\{e_i\colon t< i\leq n+1\}$. Hence it is easy to see that $V\cap S=\conv\{s_i\colon t< i\leq n+1\}$ is a $k$-dimensional subset, and it lies in $U(s)$; thus it is disjoint from $C$.

NB. It seems that the bound $n=k+t$ is optimal for almost all pairs $(k,t)$ (though for $k=0$ you may take $n=t-1$). It is easy to provide a counterexample for $k=1$, $t=2$, $n=2$, and it seems possible to generalize this example for larger values.

EDIT. On the counterexamples for the `large' $k$-dim space. Consider the Voronoi decomposition of your simplex with respect to its vertices; scale the obtained sets to the corresponding vertices to obtain disjoint closed sets $C_i'$. Now all the $k$-dim subsets not intersecting $C_i'$ are close to the boundaries of the Voronoi cells. Now it is easy to change our sets in the neighborhood of their boundaries so that the only such subsets will be very close to the boundary of the simplex. (For every cell border, It is enough to make some hollows in one part and some protuberances in the other one).

Answer by Ilya Bogdanov for Infinite domain with finite number of prime ideals(elements)

2012-06-14T17:29:54Z

For the commutative case. Take the set of all rational numbers whose denominators are coprime with a fixed integer $n$. Then the only prime ideals are generated by the prime divisors of $n$.

More generally, take any PID and take its ring of fractions wrt all the elements coprime with some fixed element; you get a desired ring.

Answer by Ilya Bogdanov for Vapnik-Chervonenkis dimension of lines in the plane

2012-05-31T09:39:12Z

If you take six lines forming the Star of David, then it is impossible to split the lines forming one large triangle from the lines forming the other one.

EDIT. Oh sorry, I misunderstood the concept. If I do understand it correctly now, the dimension is at least 6: on the picture below the 6 lines can be split in any way.

EDIT2. It is not an example, as Gjergji and Cain notice below.

Answer by Ilya Bogdanov for Inequality of arithmetic and geometric means for the lattice polytopes?

2012-05-14T23:57:50Z

This inequality does not necessarily hold, at least for $n\geq 3$. It is somehow connected with the fact that there is no Pick's formula in more than two dimensions since there exists a convex lattice polytope with a large volume but containing a small number of lattice points.

So, for instance, for $n=3$ let $M$ be the convex hull of the points $(0,0,0)$, $(1,1,0)$, $(0,1,2k)$ and $(1,0,2k)$. Then $|M\cap {\mathbb Z}^3|=4$, but $(M+M)\cap {\mathbb Z}^3\supset \{(1,1,t):0\leq t\leq 2k\}$. So $K$ and $L$ can be chosen as vertical segments containing $k$ lattice points each.

Answer by Ilya Bogdanov for bilinear equation OR diagonal matrix search

2012-04-05T13:25:12Z

As far as I understand, you can multiply your matrix from both sides by the matrix $\left(\matrix{E_p&0\cr 0&-E_r}\right)$ with a suitable sizes of unit matrices in order to obtain a matrix $B'$ with positive entries. Then Sinkhorn's theorem is applicable, as Felix mentioned.

(Surely, this theorem provides TWO diagonal matrices $D_1$, $D_2$ with positive numbers on the diagonal such that $D_1B'D_2$ is doubly stochastic. But, since these matrices are unique up to the scaling, they should coincide up to a scalar factor.)

The area of the intersection of convex sets with prescribed pairwise intersections

2012-04-03T14:57:37Z

Consider two numbers $a>b>0$. Let $A_1,A_2,A_3$ be three convex sets in ${\mathbb R}^2$ such that $\mu(A_i)=a$, $\mu(A_i\cap A_j)=b$ ($\mu$ is the usual measure on ${\mathbb R}^2$). What is the minimal possible value of $\mu(A_1\cap A_2\cap A_3)$?

Surely, if we omit the convexity assumption, the answer is trivial. But it is not necessary realizable by convex sets. Consider, for instance, the case $a=2b$: the answer is nonzero!

It seems that the optimal construction is the following one. Take a triangle $ABC$, and cut three trapezoids $A_BA_CBC$, $B_AB_CCA$, $C_AC_BBA$ (here $A_BA_C\parallel BC$, $B_A,C_A\in BC$, similar relations for the others). E.g., for $a=2b$ the altitude of the trapezoid is $2/5$ of the altitude of triangle; hence the answer in this case seems to be $1/16$.

The generalizations are also interesting. E.g., what happens if we fix the areas but omit the relation that they are equal?

Answer by Ilya Bogdanov for Approximation by polynomials

2012-03-13T22:55:39Z

For the sake of simplicity, let us assume that $[a,b]=[0,1]$. $C^k$ always means $C^k[0,1]$. We will even approximate $f$ in $C^n$-norm satisfying your additional condition.

As was mentioned in the comments, you can easily approximate $f$ together with all its derivatives up to $n$th uniformly by a polynomial. In fact, it is enough to approximate $f^{(n)}$ with an adequate accuracy: if $||f'-P'||_C<\varepsilon$ and $f(0)=P(0),$ then $||f-P||_C<\varepsilon.$
Now take the polynomials $Q_{ik}(x)$ such that $Q_{ik}^{(d)}(x_j)=0$ for all $d=0,\dots,n$ and $j=0,\dots,m$ except that $Q_{ik}^{(k)}(x_i)=1$. Such polynomials are easy to construct: for instance, one may take $$ Q_{ik}(x)=c_{ik}(x-x_i)^k\prod_{j\neq i}\left((x-x_i)^{n+1}-(x_j-x_i)^{n+1}\right)^{n+1}\;\; $$ for a suitable constant $c_{ik}.$ Let $M=\max_{i,k}||Q_{ik}||_{C^n}.$ Then, let the approximation in the previous paragraph be $\delta$-accurate with $\delta=\varepsilon/(2M(m+1)(n+1)).$ To correct the values of the polynomial and its derivatives at $x_i,$ it is enough to add the polynomials $Q_{ik}$ multiplied by the coefficients with absolute values $\leq\delta,$ hence the total error will be not more that $\delta+(m+1)(n+1)M\delta<\varepsilon.$

Answer by Ilya Bogdanov for Maximal sets of algebraic curves, closed under rotation, dilation, and translation, that pairwise intersect at most twice

2012-01-26T16:51:09Z

I hope, by "nontrivial" curves you mean the curves of infinitely many points.

For the convenience, when speaking on the similarity transformation, we always assume that they preserve the orientation.

Take an irreducible algebraic curve $C$ (we assume that it contains infinitely many points) and consider a family $F$ of all its images under the similarity transformations. We claim that if $F$ is groovy then $C$ is either a circle or a line.

Consider all the triples of distinct points on $C$. There are infinitely many pairwise similar triples among them (since the triples up to similarity form a 2-dimensional projective manifold). Let $\phi$ be the similarity transformation passing one such triple to another one; then $C$ and $\phi(C)$ share three common points, hence they should coincide. Thus we have found nan infinite group of transformation preserving $C$.

Now, if among these transformations there is one with a nontrivial scale factor, then, applying it repeatedly, you obtain infinitely many collinear points on $C$, hence $C$ is a line. The same is valid for the translations.

In the remaining case, all the transformations are rotations, and you obtain infinitely many points on one circle, unless all the angles are rational multiples of $\pi$, and there are different centers of rotation. In the latter case, though, combining these rotations you can obtain a nontrivial translation, which is impossible.

Hence all the irreducible components of the curves in a groovy family are either circles or lines. It is easy to see then that the curves themselves are circles or lines. Thus your family is the unique maximal one.

On the other hand, it seems that a family generated by a (short enough) segment of a spiral $r=a^\varphi$ is groovy.

Answer by Ilya Bogdanov for Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?

2012-01-16T13:20:07Z

A counterexample to the first question can be found along the same lines.

Let $k>2$, $n=kM$; we will choose the value of $M$ later. Partition $[n]=I_1\sqcup\dots\sqcup I_M$, $|I_s|=k$. Let $B$ be the set of all points $x$ such that for each $s\leq M$, there exist two indices $i,j\in I_s$ such that $x_i=x_j=1$. Set $B_0=B\cap F_0$, $B_1=B\cap F_1$. Then $$ |B_0|-|B_1|=\left(\sum_{i=2}^{k}(-1)^i{k\choose i}\right)^M=(k-1)^M. $$ Now let us center the spheres at the points of $B_0$. Then each odd point which is not in $B_1$ will be covered at most $k-1$ times, hence the number of points covered at least $k$ times is (at most) $|B_1|=|B_0|-(k-1)^M$. Moreover, $$ |B_0|>|B|/2=(2^k-k-1)^M/2=2^{kM-1}\left(1-\frac{k-1}{2^k}\right)^M>2^{kM-2} $$ if, for instance, $M\approx \frac{2^k}{2(k-1)}$ and $n\approx 2^{k-1}$. Hence we have found a counterexample for the first question. Moreover, we have shown that in the second one, we should have $c\leq 1$.

Answer by Ilya Bogdanov for Sufficient conditions to tell whether a surface contains a line

2011-11-23T20:00:03Z

Perhaps this is not a good answer; but I am not sure if there exists a better one.

This polynomial should be represented in a form $f=k_1f_1+k_2f_2$, where $k_1$, $k_2$ are two linear functions (such that their common zeroes form a line), $f_1$ and $f_2$ are the polynomials of degree $\leq d-1$. If such representation exists, your surface surely contains a line $k_1=k_2=0$.

Backwards, assume that such a line exists; after the coordinate change, this line is $x_1=x_2=0$. Writing $f$ as $f=x_1f_1(x_1,x_2,x_3)+x_2f_2(x_2,x_3)+f_3(x_3)$ we see that $f_3(x_3)=0$, thus obtaining a desired representation.

The answer for the projective case is just the same; of course, now the linear functions should be homogeneous.

Answer by Ilya Bogdanov for Chain of ideals in a complex algebra

2011-11-23T16:21:54Z

Let $T=\{x_i\} _ {i\in{\mathbb N}}\cup \{y_\alpha\}_{\alpha\in{\mathbb R}}$. Consider an algebra $A={\mathbb C}[T]$, and denote $I_k=\langle \{x_i\} _ {i=1}^k\cup\{x_{k+1}y_\alpha\}_{\alpha\in{\mathbb R}}\rangle$. Then none of $I_k$'s is countably generated, but $\cup_k I_k=\langle \{x_i\}_{i\in{\mathbb N}}\rangle$.

Answer by Ilya Bogdanov for Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

2011-11-09T16:19:16Z

Here is a different approach, also using a theorem; I do not know if it is elementary in your view.

Let $A$ be a set of $n$ vertices, and let $B_1,\dots,B_{n-1}$ be its subsets. Introduce $n$ variables $x_a$ ($a\in A$) and consider a system of $n-1$ linear equations of the form $\sum_{a\in B_i} x_a=0$. It has a nonzero solution $(x^0_a)_{a\in A}$. Now paint all the vertices $a:x_a^0>0$ in red, and $a:x_a^0<0$ in blue; you are done.

Right now I do not understand how to extend this argument for $k$-coloring...

Answer by Ilya Bogdanov for Walks that cannot hit the boundary

2011-10-14T17:06:14Z

In fact, you can prove that $p^+=p$ for all $p$.

Actually, consider the shortest paths from $(-n,-n)$ to $(n,n)$ and from $(-n,n)$ to $(n,-n)$ passing through $p$. Taking `pluses' of them, you should also obtain the paths of the same lengths connecting the same points. Now from the first path you obtain that the sum of coordinates of $p^+$ is the same as for $p$, and from the second path you see that the difference of coordinates is the same for $p$ and $p^+$. Hence $p=p^+$.

Comment by Ilya Bogdanov

2013-04-13T09:52:47Z

As far as I undestand, the question may be formulated as follows. We have a digraph where each vertex has both in- and out-degrees equal to 2. $n$ independent vertices are marked (there are in/outputs of the black box), and for every permutation of the marked vertices there exists an automorphism of the graph inducing exactly this permutation. Is this what you meant?

Comment by Ilya Bogdanov

2013-04-09T04:50:56Z

The approach is interesting. But it seems that you think there are $p^3$ matrices; in fact, there are $p^{p^2}$ of them. But you do not need so much, since there are less than $p^p$ distinct denominators (all costant terms are ones). This gives the estimate of about $2p^{p+1}$ coefficients to check. Unfortunately, now we have a half of this amount.

Comment by Ilya Bogdanov

2013-04-07T21:05:52Z

Does it remain for larger $k$?

Comment by Ilya Bogdanov

2013-04-07T20:50:07Z

It is so obvious that I do not think it deserves a citation.

Comment by Ilya Bogdanov

2013-03-30T08:35:21Z

In fact, this bound is tight. Look at the triangle wth vertices $(0,0)$, $(2,1)$ and $(1,2)$. Its area is $3/2$, while its "integral width" is 2. To see that, first notice that all its altitude lengths are greater than 1, hence it is enough to check only the vectors of length less than 2. This check is straightforward. So, what is this bounty for?

Comment by Ilya Bogdanov

2013-03-30T08:32:12Z

You need to be a bit more careful, since the affine transforms do not preserve scalar product. So in fact you need to put the vector orthogonal to $v$ into $(-1,1)$.

Comment by Ilya Bogdanov

2013-03-28T06:55:59Z

Considering the quadrilateral $Q$ of maximal area inscribed into $M$. THen you may pass to the parallelogram with sides parallel to the diagonals of $Q$ --- its area is at most twice the area of $M$. Hence you may restrict yourself to the lattice parallelograms only.

Comment by Ilya Bogdanov

2013-03-24T20:49:16Z

It is a well-known olympiad problem.

Comment by Ilya Bogdanov

2013-02-14T11:51:16Z

Well, the construction blows up not the higher terms, but the terms in the middle...

Comment by Ilya Bogdanov

2013-02-14T11:43:37Z

@Gerry: I feel the same...

Comment by Ilya Bogdanov

2013-02-14T07:29:37Z

I have added the way of constructing such an example.

Comment by Ilya Bogdanov

2013-02-12T06:39:58Z

That's a bit confusing. Is $x$ the same as $u$ and $G$ the same as $B(T)$? if so, as far as I understand, both $\min u$ and $\min y$ taken over all tournaments of size $n$ tend to infinity as $n\to\infty$; so, if one is bounded then $n$ is bounded as well.

Comment by Ilya Bogdanov

2013-02-07T15:16:22Z

What does "undefined" mean? Do you need the lower bound for all matrices with some prescribed values?

Comment by Ilya Bogdanov

2013-01-25T20:55:01Z

Both numbers 6 and 8 are optimal.

Comment by Ilya Bogdanov

2013-01-05T16:53:00Z

@domotorp: By a straightforward induction on $p$, the subset uncovered by $p$ hyperplanes, if nonempty, is an affine subspace of codimension at most $p$.