User ewan delanoy - MathOverflow

Approximate solutions for trisecting the angle or squaring the circle

2010-03-27T09:27:30Z

Hello all, it is well-known by transcendence results or Galois theory that famous geometric problems such as trisecting an angle or "squaring the circle" (i.e. given a disk of radius 1 construct a square of equal area) are not solvable by compasses-and-ruler only constructions. On the other side, it is equally well-known, by approximation results such as Weierstrass', that given any $\varepsilon >0$ there is a definite construction process that yields an approximate solution which is correct up to $\varepsilon$. Of course, the obvious solution is to compute the coordinates of the points you need up to the precision you need, and then place the points. This solution however relies on some classical function tables (cosine, arc cosine or the decimal expansion of $\sqrt{\pi}$) and I am wondering if there is a more "purely geometric solution" needing no calculator or tables. Specifically, for angle trisection, one could ask the following :

Define explicitly a compasses-and-ruler only algorithm with the following properties :

Initial data : a circle with center O and radius 1 cm, two points I and J on that circle such that IOJ is a straight angle, and a point M on the arc between I and J. Let us call N the point on that arc such that the angle ION is one third of IOM. The algorithm must return a point N' which is undistinguishable from N to the naked eye, and must not rely on any calculator or tables.

Either that question is interesting or it isn't. If it isn't, the "shortest number of steps" solution has a large number of steps and is only a complicated reformulation of the compute-coordinates-with-calculator method.

Every positive polynomial with rational coefficients is above a completely Q-factorized nonnegative polynomial ?

2012-02-03T18:05:51Z

This question was originally asked in stackoverflow (http://math.stackexchange.com/questions/103941/every-positive-polynomial-is-above-a-completely-q-factorized-positive-polynomial) but as it has remained without further feedback for a week I migrate it here.

Let $P$ be a unitary polynomial with rational coefficients in one variable $x$, such that $P(x) \gt 0$ for all $x \in \mathbb R$. Then $P$ is of even degree, say $2d$. Is it true that there always exist $d$ rational numbers $q_1,q_2, \ldots ,q_d$ such that

$$ (*) \ \ \ P(x) \geq \bigg( \prod_{k=1}^{d} (x-q_k)^2\bigg) $$

for all $x\in \mathbb R$ ?

I can show that the answer is YES when $d=1$ or $d=2$.

When $d=1$, P has a canonical form $(X-a)^2+b$ with $b>0$, so we may take $q_1=a$ ($a$ will be rational since the coefficients of $P$ are) and we are done.

Now assume $d=2$. Then $P$ has a global minimum $\mu_1>0$, attained at one (or several) value $\eta_1$. Then $Q=\frac{P-\mu_1}{(X-\eta_1)^2}$ is a unitary polynomial of degree $2$ in $X$ and is nonnegative everywhere, so we can write $Q=\mu_2 + (X-\eta_2)^2$ with $\mu_2 \geq 0$. If we write $P$ explicitly as $P=X^4+a_3X^3+a_2X^2+a_1X+a_0$, where $a_0,a_1,a_2$ and $a_3$ are rational, then we have

$$ Q=X^2 + (a_3 + 2\eta_1)X + (a_2 + (2a_3\eta_1 + 3\eta_1^2)) $$

So that $\eta_2=-\frac{a_3 + 2\eta_1}{2}$. We deduce the identities $$ Q=\mu_2+(X+\frac{a_3 + 2\eta_1}{2})^2 $$

$$ P=\mu_1+(X-\eta_1)^2Q=\mu_1+(X-\eta_1)^2\bigg( \mu_2+(X+\frac{a_3 + 2\eta_1}{2})^2\bigg) $$

Now $$ \Omega=\Bigg\lbrace r \in {\mathbb R} \Bigg| \forall x\in {\mathbb R}, \ P(x) \gt \frac{\mu_1}{2}+(x-r)^2\bigg( \mu_2+(x+\frac{a_3 + 2r}{2})^2\bigg) \Bigg\rbrace $$

is an open set in $\mathbb R$. It is nonempty, since by construction it contains $\eta_1$. So it will always contain a rational number $q$. Then, we may take $q_1=q$ and $q_2=-\frac{a_3 + 2q}{2}$ and (*) holds.

Intuitive and/or philosophical explanation for set theory paradoxes

2010-06-18T19:08:53Z

Every student of set theory knows that the early axiomatization of the theory had to deal with spectacular paradoxes such as Russel's, Burali-Forti's etc. This is why the (self-contradictory) unlimited abstraction axiom ($\lbrace x | \phi(x) \rbrace$ is a set for any formula $\phi$) was replaced by the limited abstraction axiom ($\lbrace x \in y | \phi(x) \rbrace$ is a set for any formula $\phi$ and any set $y$).

Now this always struck me as being guesswork ("if this axiom system does not work, let us just toy with it until we get something that looks consistent "). Besides, it is not the only way to counter those "set theory paradoxes" -there's also Neumann-Bernays-Godel classes.

So my (admittedly vague) question is : is there a way to explain e.g. Russel's paradox that does better than just saying, "if you change the axioms this paradox disappears ?" Clearly, I'm looking for an intuitive heuristic, not a technical exact answer.

EDIT June 19 : as pointed out in several answers, the view expressed above is historically false and unfair to the early axiomatizers of ZFC. The main point is that ZFC can be motivated independently from the paradoxes, and "might have been put forth even if naive set theory had been consistent" as explained in the reference by George Boolos provided in one of the answers.

Quotients of perfect powers separated by an integer

2011-12-12T08:17:39Z

Let $a_n=\frac{(n+1)^{n+2}}{n^n}$ and $b_n=\frac{(n+2)^{(n+1)}}{(n+1)^{n-1}}$. Then it is easy to see that $a_n \leq b_n$ for all integers $n\geq 1$ (because the sequence $(1+\frac{1}{n})^n$ is increasing).

My question is : is there always an integer between $a_n$ and $b_n$ ? This holds for $1 \leq n \leq 100$.

One-sided version of the "best approximation polynomial" : Upper polynomial approximations

2011-10-31T09:20:05Z

Let $X$ be a finite subset of $\mathbb R$ and let $f : X \to {\mathbb R}$. Suppose we want to approximate $f$ by a polynomial $g$ of fixed degree $d\geq 1$ with the additional condition $g\geq f$. Let

$$ S=\lbrace h : X \to {\mathbb R} | h \geq f, \ h {\rm\ is \ the \ restriction \ of \ a \ polynomial \ } g {\rm \ of \ degree \ } d\rbrace $$

We equip $S$ with the usual partial ordering ( $h_1 \leq h_2$ iff $h_1(x) \leq h_2(x)$ for all $x\in X$). Let $M(S)$ denote the set of minimal elements of $S$. Is it true that $M(S)$is always finite ? Also, is there an effective bound for $|M(S)|$ in terms of $d$ ?

When $d=1$, it seems that $|M(S)| \leq 3$ (this bound is attained when the graph of the function is a trapezium for example).

UPDATE : as noted in the comment below, $M(S)$ is not finite. But $S$ is convex, so the convex hull $C(M(S))$ of $M(S)$ is contained in $S$, and it seems that the set of extremal points in $C(M(S))$ (denote it by $E(S)$) is finite.

Smallest size for an incomplete tournament with property $S_k$

2011-10-22T13:45:02Z

By a well-known probabilistic argument due to Erdos, if $k>1$ is an integer then for all large enough $n$, there an asymmetric relation $R$ on $X=\lbrace 1,2, \ldots ,n \rbrace$ (i.e. $R \subseteq X^2$ and $\forall (x,y) \in R, (y,x)\not\in R$ ) such that for any $k$ elements $x_1,x_2, \ldots x_k$ in $X$, there is a $y\in X$ such that $x_1Ry, x_2Ry, \ldots ,x_kRy$ (this is the famous ``$S_k$" property).

Denote by $f(k,n)$ the smallest size of such a relation, when it exists (here size means the cardinality of $R$). Clearly $f(1,n)=n$ (and the optimal solutions are the cycles of length $n$). What bounds are known for $f(k,n)$ when $k>1$ ?

mutually incompatible abstraction terms?

2011-09-10T11:02:06Z

If $\phi$ is any formula of set theory with just one free variable $x$, the abstraction term $A_{\phi}=\lbrace x | \phi(x) \rbrace$ is either a set or a proper class. Assume that ZFC is consistent, or any large cardinal axiom you like. Then my question is, are there two formulas $\phi$ and $\psi$ such that ZFC+($A_{\phi}$ is a set) is consistent, ZFC+($A_{\psi}$ is a set) is consistent also, but ZFC+($A_{\phi}$ and $A_{\psi}$ are both sets) is not?

UPDATE 09/15/2011 : to avoid "cheating" as in François Dorais' answer, we may introduce the following additional constraint : if $T$ is any theory extending $ZFC$, say that the abstraction term $A_{\phi}=\lbrace x | \phi(x) \rbrace$ is small in $T$ if $T$ proves that $A_{\neg \phi}$ is not a set ; for example, if $\phi(x)$ is "x is an accessible ordinal" or "all cardinals below the ordinal $x$ are not measurable" or "all cardinals below the ordinal $x$ are not Mahlo" then $A_{\phi}$ will be small, but this will not be the case if $\phi$ is an undecidable statement independent of $x$ as in Francois Dorais' answer.

The question then becomes, are there two formulas $\phi$ and $\psi$ such that $A_{\phi}$ and $A_{\psi}$ are both small in $ZFC$, ZFC+($A_{\phi}$ is a set) is consistent, ZFC+($A_{\psi}$ is a set) is consistent also, but ZFC+($A_{\phi}$ and $A_{\psi}$ are both sets) is not?

Comparing hitting probabilities for two different random walks

2011-08-15T18:10:50Z

Let $p$ be a probability in $]0,1[$, and let $(X^p_i)_{i \geq 1}$ be a i.i.d. family of variables with law $P(X=1)=p, P(X=-\frac{p}{1-p})=1-p$ (so that $E(X)=0$). Set $S^p_n=\sum_{k=1}^{n} X^p_k$ for $n\geq 1$, let $e(p,n)$ denote the probability that at least one of $S^p_1,S^p_2, \ldots ,S^p_n$ is positive (which means that the random walk reaches a positive value at least once during the first $n$ steps ). It is well known that for a fixed $p$, $e(p,n) \to 1$ when $n\to +\infty$.

Let $p\neq q$ be two probabilities. For large enough $n$, shall we have $e(n,p) \lt e(n,q)$ or $e(n,p) \gt e(n,q)$ ?

"Unknot" algebraic set defined by two mutually dependent set of variables

2011-06-05T12:01:25Z

Let $n$ be an integer $\geq 4$, and let $V \subseteq {\mathbb C}^{2n-1}$ be the set of all $(a_1,a_2, \ldots ,a_n,b_1,b_2, \ldots ,b_{n-1}) \in {\mathbb C}^{2n-1}$ such that the derivative of the polynomial $ P=\prod_{k=1}^{n} (x-a_k)$ is exactly $n\prod_{k=1}^{n-1} (x-b_k)$. Then $V$ is a closed algebraic set in $ {\mathbb C}^{2n-1}$ : it can be defined by the $n-1$ equalities

$\sigma_k(b_1,b_2, \ldots ,b_{n-1})=\frac{n-k}{n}\sigma_k(a_1,a_2, \ldots ,a_{n-1},a_n) (1 \leq k \leq n-1)$,

where $\sigma_k$ denotes the $k$-th symmetric polynomial.

My question is, can $V$ be described as the image of a "rational" map, i.e. are there rational functions $f_1,f_2 \ldots f_{2n-1}$ in $r$ variables $y_1,y_2, \ldots ,y_r$ (where $r$ is another integer ) such that $V$ is exactly the image of the map $(f_1,f_2 \ldots f_{2n-1}): {\mathbb C}^{r} \to {\mathbb C}^{2n-1}$ ? Is $V$ a finite union of such images?

Is there a good explanation for this fact on pairwise independent variables?

2011-06-02T14:26:19Z

Let $X_1,X_2,X_3,X_4$ be four random variables with standard Bernoulli distribution (i.e. $P(X_i=0)=P(X_i=1)=\frac{1}{2}$ for $1 \leq i \leq 4$) and such that any two of those four variables are independent.

Then the fourtuple $\overrightarrow{X}=(X_1,X_2,X_3,X_4)$ takes at least one of the three values $(0,0,0,0),(0,0,0,1)$ or $(0,0,1,0)$ with positive probability.

This surprising fact can be shown by brute force: what we have is essentially a system of linear equalities and inequalities in 16 variables corresponding to the distribution of $\overrightarrow{X}$. The proof is straightforward but not very illuminating. Are there better explanations?

UPDATE 22:15 Actually, the following stronger property holds : for any $(a,b,c,d)$ in $\lbrace 0,1 \rbrace ^4$, the event $(X_1,X_2)=(a,b) \Rightarrow (X_3,X_4)=(c,d)$ has probability $<1$ (in this sense, $(X_3,X_4)$ cannot be "dependent" on $(X_1,X_2)$).

Sufficiently random sample

2011-05-14T09:12:35Z

Let $d$ be an integer $\geq 2$, and let $\Omega = \lbrace 0,1 \rbrace^d$, $A \subseteq \lbrace 0,1 \rbrace^2 $ and $i,j$ integers with $1 \leq i < j \leq d$. If we select an element $(x_1,x_2, \ldots, x_d)$ in $\Omega$ randomly, the probability $p(\Omega,i,j,A)$ that $(x_i,x_j)\in A$ is exactly $\frac{|A|}{4}$.

If $\Omega'$ is a subset ("sample") of $\Omega$, we may similarly define $p(\Omega',i,j,A)$. We say that $\Omega'$ is an efficient substitute for $\Omega$ if $p(\Omega',i,j,A)=p(\Omega,i,j,A)$ for all $i,j$ and $A$.

We denote by $f(d)$ the smallest possible size for an efficient substitute for $\Omega$. We have the trivial bound $f(d) \leq 2^d$ (take $\Omega'=\Omega$) and , for example, $f(3)=4$ (take $\Omega'=\lbrace (x,y,x+y-2xy) |(x,y) \in \lbrace 0,1 \rbrace^2 \rbrace$). What is the value of $f(d)$ in general?

Answer by Ewan Delanoy for Splitting an evaluated complete graph

2011-04-12T17:55:05Z

The answer is NO, at least for $n=4$. I show here that $\eta(4) \leq 7$. So let $\omega$ be a valuation on $K_7$ ; we will show that it is $4$-valid.

First, we need some notation : for $A \cup B$ a nontrivial partition of $V=\lbrace 1,2,3, \ldots ,7\rbrace$, let

$$ s(A,B)=\sum_{(x,y) \in A \times B} \omega(\{ x,y \}), \ f(A)=s(A,V\setminus A). $$

We can now write some useful relations :

$$ f( i,j)=f(i)+f(j)-2\omega(i,j), f(i,j,k)=f(i)+f(j)+f(k)-2(\omega(i,j)+\omega(i,k)+\omega(j,k)) $$

(where, for simplicity, we write $f(i)$ instead of $f(\lbrace i \rbrace)$, $f(i,j)$ instead of $f(\lbrace i,j \rbrace)$, etc).

Assume, by contradiction, that $\omega$ is not $n$-valid. Then the values of $f$ are all $1,2$ or $3$ modulo $4$. For convencience's sake, we now take $\omega$ and $f$ to take values in $\frac{\mathbb Z}{4\mathbb Z}$.

By easy double-counting, the sum $f(1)+f(2)+f(3)+ \ldots +f(7)$ is even (this is twice the sum of all the values of $\omega$), so that at least one $f(i)$ is even. Then $f(i)=2$. So the set $X=\lbrace i\in [1...7] | f(i)=2 \rbrace$ is not empty.

For any $i,j$ in $X$, we have $f(i,j)=4-2\omega(i,j)$, hence $\omega(i,j)=1$ or $3$ and $2\omega(i,j)=2$ in both cases. If $X$ contained more than two elements, we could find $i \lt j \lt k$ in $X$ and compute $f(i,j,k)=f(i)+f(j)+f(k)-2(\omega(i,j)+\omega(i,k)+\omega(j,k))=2+2+2-2-2-2=0$, a contradiction. So $|X| \leq 2$.

Similarly, we show that the set $Y=\lbrace i\in [1...7] | f(i)=1 \rbrace$ contains at most two elements. Reasoning as before, we have $2\omega(i,j)=0$ for any $i \lt j$ in $Y$. Recall that some $x$ in $[1...7]$ satisfies $f(x)=2$. We have $f(x,i,j)=-2(\omega(x,i)+\omega(x,j))$. By the pigeon-hole principle, if we had $|Y| \gt 2$ we cound find $i \lt j$ in $Y$ such that $\omega(x,i)=\omega(x,j)$, hence $f(x,i,j)=0$, a contradiction. So $|Y| \leq 2$.

Using the symmetry $x \mapsto -x$ in $\frac{\mathbb Z}{4\mathbb Z}$, we see that $|Y'| \leq 2$ where $Y'=\lbrace i\in [1...7] | f(i)=3 \rbrace$.

So, we have shown that on $[1..7]$, $f$ takes each of its three values ($1,2$ or $3$ mod $4$) at most twice. This contradicts the pigeonhole principle and finishes the proof.

Complex version of Farkas' lemma

2011-04-10T09:32:22Z

It is well known result of linear optimization theory that, if a finite set $S$ of linear inequalities in real variables $x_1,x_2, \ldots ,x_n$ implies a linear inequality $i$ in $x_1,x_2, \ldots ,x_n$, then $i$ can be written as a positive linear combination of the inequalities in $S$.

I wonder if an analogous property holds for moduluses of complex variables : let $A=(a_{ij}) (1 \leq i \leq p, 1 \leq j \leq n)$ be a matrix in ${\cal M}_{p,n}({\mathbb C})$ and $B=(b_1,b_2, \ldots b_p)^{T}$ be a column matrix in ${\cal M}_{p,1}({\mathbb R}^{+})$. Then we may denote by $|AZ| \leq B$ (where $Z=(z_1,z_2, \ldots z_n)^{T}$ is a column matrix in ${\cal M}_{n,1}({\mathbb C})$ ) the finite set of modulus constraints $\big| \sum_{j=1}^{n}a_{ij}z_j \big| \leq b_i$ for $1\leq i\leq p$. Suppose this set of constraints implies another modulus constraint (*), say $\big| \sum_{j=1}^{n}c_{j}z_j \big| \leq d$, with $c_j \in {\mathbb C}$ and $d \geq 0$.

The question, then, is : can (*) be deduced linearly from $S$ ? In other words, are there scalars ${\lambda}_1, {\lambda}_2, \ldots ,{\lambda}_p$ in $\mathbb C$ with

$$ \sum_{i=1}^{p}\lambda_ia_{ij}=c_j \ ({\rm for} \ 1 \leq j \leq n), \ \ \sum_{i=1}^{p}|\lambda_i|b_i \leq d. $$

Structure of nonaveraging sets of integers

2011-04-02T12:55:05Z

A set of integers is said to be nonaveraging if it contains no three-term arithmetic progression. I call a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ optimal when it has maximal cardinality.

There is a regularly updated website on nonaveraging sets records at http://www.math.uni.wroc.pl/~jwr/non-ave/DATABASE.TXT. Most of the research done on upper bounds for nonaveraging subsets of $\lbrace 1,2, \ldots ,n \rbrace$ (by Roth, Bourgain, Gowers, Tao, Green and others) involves randomness one way or another (be it in the form of Fourier analysis, extremal graph theory or ergodic theory) , and Behrend's lower bound is nonconstructive.

Despite the randomness, the optimal nonaveraging sets display some structure :

When $n=20$, there are two optimal solutions, which are $B \cup (B+5) \cup \lbrace 18 \rbrace$ and $B' \cup (B'+5) \cup \lbrace 3 \rbrace$, where $B=\lbrace 1,2,9,15 \rbrace$ and $B'=\lbrace 1,7,14,15 \rbrace$. When $n=30$, there is a unique optimal solution, $B \cup (B+19)$, where $B=\lbrace 1,3,4,8,9,11 \rbrace$. Looking at larger examples from the abovementioned website, the decomposition "two copies+error term" seems to persist, which inspires me the following list of (increasingly strong) conjectures :

** Conjecture 1. ** There is a function $E(n)$ tending to $+\infty$ when $n$ tends to infinity, such that for any optimal nonaveraging subset $X$ of $\lbrace 1,2, \ldots ,n \rbrace$ we can write $X=B \cup (B+t) \cup C$ for some nonzero integer $t$ and some $B,C \subseteq \lbrace 1,2, \ldots ,n \rbrace$ and $|B| \geq E(n)$.

** Conjecture 2. ** There is a function $\varepsilon(n)$ tending to $0$ when $n$ tends to infinity, such that for any optimal nonaveraging subset $X$ of $\lbrace 1,2, \ldots ,n \rbrace$ we can write $X=B \cup (B+t) \cup C$ for some nonzero integer $t$ and some $B,C \subseteq \lbrace 1,2, \ldots ,n \rbrace$ with $|C| \leq n\varepsilon(n)$.

** Conjecture 3. ** There is a function $\varepsilon(n)$ tending to $0$ when $n$ tends to infinity, such that for any optimal nonaveraging subset $X$ of $\lbrace 1,2, \ldots ,n \rbrace$ we can write $X=B \cup (B+t) \cup C$ for some nonzero integer $t$ and some $B,C \subseteq \lbrace 1,2, \ldots ,n \rbrace$ with $|C| \leq |X|\varepsilon(n)$.

Note that the two copies $B$ and $B+t$ are necessarily disjoint since $X$ is nonaveraging. Also, for each conjecture we have a weaker variant where "any optimal $X$" is replaced with "at least one optimal $X$".

Conjectures 2 and 3 may be out of reach but conjecture 1 seems really easier because containing no two copies of a set of size at least $k$ is a much stronger requirement than being nonavering, so that the corresponding optimal sets should be much smaller. Can anyone supply a proof?

"Consecutive" irreducible polynomials

2011-03-29T07:07:02Z

If $P\in {\mathbb Z}[X]$ is a polynomial of degree $2$, then it is easy to see that for any integer $m$, at least one of the polynomials $P-(m+1),P-(m+2),P-(m+3),P-(m+4)$ is irreducible in ${\mathbb Z}[X]$. I believe a much stronger property holds, namely that for any degree $d\geq 2$ and length $l\geq 1$, there is a constant $C(d,l)$ such that for any polynomial $P\in {\mathbb Z}[X]$ of degree $d$, in any interval $I=\lbrace m+1,m+2, \ldots ,m+C(d,l) \rbrace$ we may encounter a subinterval of length $l$, $I'=\lbrace m+j+1,m+j+2, \ldots ,m+j+l \rbrace$ with $j+l \leq C(d,l)$ such that $P-a$ is irreducible in ${\mathbb Z}[X]$ for any $a\in I'$. Is that property already known to be true, and are bounds known for $C(d,l)$ ?

are there infinitely many triples of consecutive square-free integers?

2011-03-27T17:11:52Z

The title says it all ... Obviously, any such triple must be of the form $(4a+1,4a+2,4a+3)$ where $a$ is an integer. Has this problem already been studied before ? The result would follow from Dickson's conjecture on prime patterns, which implies that there are infinitely many integers $b$ such that $4(9b)+1,2(9b)+1$ and $4(3b)+1$ are all prime (take $a=9b$).

Best rational approximation in a special sense

2011-03-20T10:45:30Z

Let $\alpha$ be an irrational number, $n\geq 1$ and

$ X_n=\lbrace (x,y) \in {\mathbb Z}^2 | |y| \leq n, \ x+y\alpha >0 \rbrace$

Now let $(x_n,y_n)$ minimize the quantity $x+y\alpha$ on $X_n$. This pair is unique because $\alpha$ is irrational. Now the problem is to deduce all the "location" of $\alpha$ from the three integers $n,x_n$ and $y_n$ only.

The two simplest cases are :

$x_n=0,y_n=1$. This is equivalent to $0 < \alpha < \frac{1}{n+1}$.

$x_n=1,y_n=-2$. This is equivalent to $\frac{1}{2}-\frac{1}{2m} < \alpha < \frac{1}{2}$ (where $m$ is the smallest odd integer $>n$).

More generally, it seems that for any triple $(n,x,y)$, the set $Y(n,x,y)$ of all irrationals $\alpha$ yielding $x_n=x,y_n=y$, is either empty or an interval $[A(n,x,y),B(n,x,y)] \setminus {\mathbb Q}$. Is that true, and are there recursive formulas to compute $A(n,x,y)$ and $B(n,x,y)$ ?

This problem is certainly related to continued fractions and best approximations in the usual sense, but I don't see how to make the connection effective.

Answer by Ewan Delanoy for Recurrence Equations for Matrix Determinant

2011-03-12T08:43:55Z

To sum it all in one sentence, this is the Horner method applied to the computation of the characteristic polynomial of $A$. Your algorithm computes the whole charcateristic polynomial of $A$, in fact, and the determinant is only the last offshoot.

Formally, let $$X^n+\sum_{k=0}^{n-1}a_kX^k$$ be the characteristic polynomial of $A$. Thus, for example, $-a_{n-1}$ is the trace of $A$, and $(-1)^{n}a_0$ is the determinant of $A$. An easy induction on $k$ shows that

$$ B_k=A^{k-1}+ \sum_{j=0}^{k-2}a_{n+1-k+j}A^j$$

for all $k$. Finally, the Cayley-Hamilton theorem shows that $AB_n$ is exactly $-a_0I$.

Smallest integer not divisible by integers in a finite set

2010-03-08T21:23:03Z

Hello all, if $a_1,a_2, \ldots a_t$ are $t$ integers $\geq 2$, the set $G(a_1,a_2, \ldots a_t)=\lbrace N \geq 1 |$ In any sequence of $N$ consecutive integers there is at least one not divisible by any of $a_1,a_2, \ldots a_t\rbrace$ is nonempty (it contains $a_1a_2 \ldots a_t$) so it has a minimal element which we denote by $g(a_1,a_2, \ldots a_t)$.

Question 1 : Is there a uniform bound $\gamma (t)$, depending only on $t$, such that $\gamma (t) \geq g(a_1,a_2, \ldots a_t)$ for any $a_1,a_2, \ldots a_t$ ? For example, we may take $\gamma(2)=4$.

Question 2 : If $\gamma$ is well-defined, are any asymptotics known about $\gamma(t)$ ?

Analogue of an orthogonal subspace in a noneuclidian normed space

2011-02-07T18:46:48Z

This question is related to http://mathoverflow.net/questions/50600/an-existence-question-on-linear-map. If the answer to this question is yes, it would solve the abovementioned other MO question.

We equip ${\mathbb R}^3$ with the $\ell_3$ norm $||(x,y,z)||=(|x|^3+|y|^3+|z|^3)^{\frac{1}{3}}$. Is it true that, for any vectorial plane $V$ in ${\mathbb R}^3$, we can find a vector $w$ not in $V$ such that $||w+v|| \geq ||v||$ for all $v \in V$ ? It is easily seen that this property holds for some norms (such as the $\ell_2$ norm) and fails for others, such as the $\ell_{\infty}$ norm.

Minimal subset of axioms for ZFC

2010-12-05T13:29:58Z

Hello all, one may look for "minimal system of axioms" for ZFC (or any other theory) in the following (unusual) sense : say that a subset S of ZFC is "sufficient" if there is an explicit procedure that constructs a model of ZFC from any model of S.

Thus, for example, ZF is sufficient since inside ZF we can construct Godel's universe L which is a model for ZFC. My questions : are minimal sufficient subsets of ZFC known? Is extensionality+infinity+(power set)+(separation scheme) sufficient?

Answer by Ewan Delanoy for Can an integer or rational sequence satisfy some bounded order recurrence $\mod \ $ almost all primes but doesn't satisfy such in $\mathbb{Q}$?

2011-02-04T17:41:16Z

This is not a new answer but a comment too long to fit in the usual comment format. It answers the "linear" variant of the problem suggested by Qiaochu. So let us suppose that there is an infinite set $\cal P$ of primes such that the sequence $(a_n)_{n\geq 1}$ satisifies some linear recurrence modulo $p$ for every $p\in {\cal P}$ .

Now consider the function $A$ defined by $A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$ for all $n \geq 0$ . Let $\Omega$ be the set of all integers $t\geq 1$ such that the vectors $A(i+1),A(i+2), \ldots ,A(i+t)$ are linearly dependent over $\mathbb Q$ for some $i$. Then $r+1\in \Omega$ so $\Omega$ is nonempty. Let $t$ be the smallest element in $\Omega$ , and pick up $i$ such that $A(i+1),A(i+2), \ldots ,A(i+t)$ are linearly dependent over $\mathbb Q$. By the choice of $t$, we have $t \leq r+1$ and $A(i+1),A(i+2), \ldots ,A(i+t-1)$ are linearly independent over $\mathbb Q$, so the last vector $A(i+t)$ is a linear combination of $A(i+1),A(i+2), \ldots ,A(i+t-1)$ :

$$ (*) : A(i+t)=\sum_{k=1}^{t-1} \beta_k A(i+k)$$

for some coefficients $\beta_1,\beta_2, \ldots ,\beta_k \in {\mathbb Q}$ . Now define a new sequence $(b_n)_{n \geq i}$ by

$$ b_n=a_{n+t}-\sum_{k=1}^{t-1} \beta_k a_{n+k}$$

By (*) above, the first $r$ values of $(b_n)_{n \geq 1}$ are $0$ (in $\mathbb Q$). Now for $p\in {\cal P}$ , the sequence $(b_n \ ({\rm mod} \ p))_{n \geq i}$ satisifies a linear recurrence of order $r$, ans starts with $r$ zeroes. So that sequence is identically zero. We deduce that $p$ divides $b_n$ for any $p\in {\cal P}$ and $n \geq i$ , so that $(b_n)_{n \geq i}$ is identically $0$ in $\mathbb Q$.

So we see that $(*)$ still holds when $i$ is replaced by any $n\geq i$ , and that the initial sequence $(a_n)_{n\geq 1}$ eventually satisfies a linear recurrence of degree $\leq r$ .

Answer by Ewan Delanoy for Can an integer or rational sequence satisfy some bounded order recurrence $\mod \ $ almost all primes but doesn't satisfy such in $\mathbb{Q}$?

2011-02-04T15:46:02Z

The answer to your question is NO. In fact, your hypothesis says that there is an infinite set $\cal P$ of primes such that for each $p\in {\cal P}$ there is a function $f_p$ from ${\mathbb Z}_p^r$ to ${\mathbb Z}_p$ such that the sequence $(a_n)_{n\geq 1}$ satisfies $$ a_{n+r+1} \equiv f_p(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r}) \ ({\rm mod} \ p)$$ for all $n\geq 0$ and $p\in {\cal P}$ .

Now consider the function $A$ defined by $A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$ for all $n \geq 0$ . If $A$ is injective, the sequence $(a_n)_{n\geq 1}$ satisfies a recurrence of degree $r$ in $\mathbb Q$ . If $A$ is not injective, then there are integers $i \lt j$ such that $A(i)=A(j)$ . Then the values $a_{i+r+1}$ and $a_{j+r+1}$ agree modulo all primes in $\cal P$, and are therefore equal in $\mathbb Q$. By induction, we see that the sequence $(a_n)_{n\geq 1}$ is eventually $(j-i)$ -periodic. Then a (more delicate) construction shows that $(a_n)_{n\geq 1}$ still satisfies a recurrence of degree $r$ in $\mathbb Q$

Which polynomials arise as formulas for a conjugate

2011-01-28T12:23:24Z

For any integer $r \geq 2$, et $V_r$ be the set of polynomials $Q \in {\mathbb Q}[X]$ of degree $r-1$ such that there is an algebraic number $\alpha$ of degree $r$ , such that $Q(\alpha)$ is a conjugate of $\alpha$. It is not hard to see that $V_2$ consists exactly of $X$ and all the polynomials $a_0-X$, for $a_0\in {\mathbb Q}$. Have the $V_r(r \geq 3)$ been studied? Is anything known about $V_3$ ?

Strengthening of Dirichlet's theorem on arithmetic progressions

2010-03-05T05:52:30Z

Hello all, Dirichlet's famous theorem asserts that any arithmetic progression $\lbrace ax+b | x \in {\mathbb N}\rbrace$ contains infinitely many primes if a and b are relatively prime.

I am wondering if the following strengthening of Dirichlet's theorem is also true :

Let $a,b$ be relatively prime integers as above. Then there is a uniform bound $g(a,b)$ such that any interval $\lbrace x+1,x+2, \ldots ,x+g(a,b)\rbrace$ of $g(a,b)$ successive integers contains at least one integer $y$ which is congruent to $b$ modulo $a$ and which is not divisible by any integer between $x+1$ (inclusive if $y\neq x+1$) and $y$ (exclusive).

Without the uniform bound, this would be a tasteless easy consequence of Dirichlet's theorem. With the bound, however, it becomes stronger than Dirichlet's theorem.

Perhaps the two are in fact equivalent ?

Simplest examples of unique-solution and unsolvable-without-backtracking Sudoku-like problems

2011-01-04T09:38:29Z

The Sudoku game admits a broad generalization as follows : let $r$ be an integer $\geq 2$ and let $X$ be a finite set, and ${\cal X}$ be a collection of $r$-subsets of $X$ (i.e, a $r$-uniform hypergraph on $X$). We call any mapping $X \to \lbrace 1,2, \ldots ,r\rbrace$ a coloring of $X$.

Then, the Sudoku-like problem associated to any partial colouring $g$ of $X$ (i.e. $g$ is a mapping from a subset of $X$ to $\lbrace 1,2, \ldots ,r$) is to extend $g$ to a colouring $f$ such that $f$ restricts to a bijection onto $\lbrace 1,2, \ldots ,r\rbrace$ (a "rainbow coloring") on each $X\in {\cal X}$. To avoid trivialties, we always assume that $X$ is not fully colored from the start, i.e. that $g$ is not defined on the whole of $X$.

We say that a Sudoku-like problem is perfect if it admits a unique solution, and reducible if there is a non-backtracking rule that allows one to deduce the color of an initially uncolored vertex $x\in X$ (formally this means that $g$ is not defined at $x$ and that there is a color $c\in \lbrace 1,2, \ldots ,r$ such that either (1) for any color $c' \neq c$ there is a $Y\in {\cal X}$ containing $x$ such that $c'\in g(Y)$ or (2) for any vertex $x' \neq x$ there is a $Y\in {\cal X}$ containing $x'$ such that $c\in g(Y)$).

Perfect irreducible Sudoku-like problems do exist (the ordinary Sudoku problem in the end of David Eppstein's arXiv paper http://arxiv.org/abs/cs/0507053v1 is one such). It is natural then to look for "simpler" perfect irreducible Sudoku-like problems, i.e. with the smallest possible value for $r$, and with as few hypergarph edges as possible. It is easy to see that we must have $r>2$. Are there examples with $r=3$ ?

example just slightly better than the greedy construction

2010-12-31T21:23:04Z

Roth's theorem provides an estimate for the largest size of a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ (a set of integers is nonaveraging if it does not contain any nontrivial three-term arithmetic progression).

If we try to construct such a nonaveraging subset "naively" and "greedily", we obtain a Cantor subset (the integers $n$ such that the ternary expansion of $n-1$ does not contain a 2), whose density in $\lbrace 1,2, ... ,n \rbrace$ is $\frac{1}{n^{1-\frac{\log(3)}{log(2)}}}$. This is known to be far from optimal, since Behrend's construction (based on projecting a sphere onto the interval $[1(...)n]$) yields a set of density around $\frac{1}{2^{\sqrt{8\log_2(n)}}}$ (Elkin improved this, but this is not our concern here ; see http://gilkalai.wordpress.com/2008/07/10/pushing-behrend-around/). Behrend's construction is non-explicit in that it uses the pigeonhole principle, ans states that some radius provides us a sphere having enough points.

Since the gap between the two is huge, one may ask if there is a more "effective" construction explaining why the greedy algorithm does not produce an optimal result, in the following sense :

Let us denote by $C$ the set of all integers such that the ternary expansion of $n-1$ does not contain a 2, so that the greedy algorithm produces $C \cap \lbrace 1,2, \ldots ,n \rbrace$. Now, is there an infinite nonaveraging subset $T$ of $\mathbb N$, such that $|C \cap \lbrace 1,2, \ldots ,n \rbrace | < |T \cap \lbrace 1,2, \ldots ,n \rbrace |$ for all large enough $n$ ?

Update 02/01/2001 : to avoid "parasitic" and non-explicit examples as explained in fedja's comments, one may impose the additional hard requirement that $T$ is constructed by first imposing a condition of the form $T \cap X_0=Y_0$ where $X_0$ is a finite set and then filling $T$ greedily.

Answer by Ewan Delanoy for Does every symmetric group S_n have a single element of maximal word norm?

2010-12-14T08:48:36Z

A more explicit version of Qiaochu's answer : $S_n$ can be viewed as a Coxeter group of type $A_{n-1}$. The maximal length is $\frac{n(n-1)}{2}$, achieved by the element $$s_1(s_2s_1)(s_3s_2s_1) \ldots (s_{n-1}s_{n-2} \ldots s_2s_1)$$.

This is a classical result in Coxeter groups theory. Sketch of the proof : for each $i \in [1,n-1]$ let $G_i$ be the so-called parabolic subgroup generated by $T_i=\lbrace s_1,s_2, \ldots ,s_n \rbrace $. For any $w\in G_k (1 \leq k \leq n-1)$ we can write $w=w_1w_2w_3 \ldots w_r$ where each $w_i \in T_k$ and $r$ is minimal. Among all those decompositions, we choose the one with as many generators in $T_{k-1}$ on the left as possible. This shows that $w$ can be written $w=w'x$, with $w'\in G_{k-1}$, and $x\in X_k$ where $X_k$ consists of the element $x\in G_k$ all of whose minimal decompositions start with $s_k$.

It is not hard to show that the pair $(w',x)$ is unique (this is because $G_{k-1}$ and $X_k$ are disjoint) and trivially we have $l(w)=l(w')+l(x)$. By induction, any $w\in S_n$ can be written uniquely $w=x_1x_2 \ldots x_n$, where each $x_i$ is in $X_i$, and furthermore $l(w)=l(x_1)+l(x_2)+ \ldots +l(x_n)$.

Now, when the group is $S_n$ it is a straightforward exercise to show that $$X_k=\lbrace s_{k},s_{k}s_{k-1}, \ldots, s_{k}s_{k-1} \ldots s_{2}s_{1} \rbrace$$ for any $k$. Therefore $X_k$ has a unique element of maximal length, $\xi_k=s_{k}s_{k-1} \ldots s_{2}s_{1}$, and we deduce that $S_n$ has a unique element of maximal length which is the product $\xi_1\xi_2 \ldots \xi_{n-1}$.

Answer by Ewan Delanoy for Cantor's argument revisited

2010-11-28T09:52:34Z

If I understood the OP correctly, the problem can be stated as follows :

Problem 1. Let $X$ be a set, let $F:{\cal P}(X) \to X$ , and let $A$ be defined as above: $$A=\lbrace F(Z) | Z\subseteq X, F(Z) \not\in Z\rbrace.$$ Find a definable $B$ (in terms of $F$) such that $B \neq A$ and $F(B)=F(A)$.

Now Problem 1 is equivalent to the simpler problem :

Problem 2. Let $Y$ be a set and let $Y'$ be a nonempty subset of $Y$. Find a definable $y_0$ (in terms of $Y$ and $Y'$) which is in $Y'$.

The interesting and nontrivial part of the equivalence is of course, to show that we can solve Problem 2 if we can solve Problem 1. Here is how. Let $Y$ and $Y'$ be as above. Take two elements $a,b$ and a countable set $W=\lbrace w_k \rbrace_{k \geq 0}$ outside of $Y$. Now define $X$ to be the disjoint union of $\lbrace a,b \rbrace$ and $Y \times W$, and define $F : {\cal P}(X) \to X$ by:

$F(\lbrace (y,w_0) \rbrace)=a$ , if $y\in {Y'} $ ,
$F(\lbrace (y,w_{k+1}) \rbrace)=(y,w_k)$ , for all $y\in Y$ and $k\ge0$ ,
$F(X)=a$ , and
$F(Z)=b$ for all other subsets $Z$ of $X$ (thus $F(\emptyset)=b$).

Now, by construction, $A=X$, and any solution $B$ to Problem 1 is of the form $\lbrace (y,w_0) \rbrace$ for some $y\in Y'$, thereby solving Problem 2.

Finite interpolation by nondecreasing indefinitely differentiable functions in a finite-dimensional space

2010-11-16T17:11:48Z

Some time ago, I asked about inite interpolation by a nondecreasing polynomial here at http://mathoverflow.net/questions/16673/finite-interpolation-by-a-nondecreasing-polynomial. This turned out to be an already solved problem; it also turned out that the degree of the solution could not be bounded in terms of the number of interpolation points alone.

My new question is: if we are willing to replace polynomials by another vector space V of indefinitely differentiable functions, then we can we achieve something better than with polynomials, in the sense that V is finite-dimensional?

Formally, fix $x_1 \lt x_2 \lt \ldots \lt x_n$ and let $y_1 \leq y_2\leq \ldots \leq y_n$ vary. We consider the system $(S)$ made of the $n$ interpolation constraints $f(x_i)=y_i$ for $i$ between $1$ and $n$. Is there a finite-dimensional subspace $V$ of ${\cal C}^{\infty}([x_1,x_n],{\mathbb R})$ such that for any $y_1 \leq y_2\leq \ldots \leq y_n$ , there is a solution to $(S)$ which is nondecreasing and also in $V$?

Comment by Ewan Delanoy

2012-04-22T14:39:21Z

Interesting. "Empty" is not the same thing as "vicious" indeed.

Comment by Ewan Delanoy

2012-02-04T16:17:58Z

(precedent comment, continued) This does not happen because, roughly speaking, polynomials are very regular objects and we have uniform bounds for everything. I'm still thinking about how to show this rigorously with a minimum of notation.

Comment by Ewan Delanoy

2012-02-04T16:16:51Z

@Will : I am now convinced that your construction works, but I still think that your proof that it works is incomplete because there's a "uniformity" argument lacking. What I mean is that we might have $P-(\prod_{k}(x-d_k))^2$ nonnegative everywhere except on an interval $[N,N+1]$, say, with $N$ tending to infinity as the $d_k$'s gets closer to $a_k$'s. So that the construction would work both for small x and for large x, but not in-between.

Comment by Ewan Delanoy

2012-02-03T21:19:54Z

Of course, $P(x)=(x-\sqrt{2})^2$ does not satisfy my hypotheses, but it illustrates my point : you can find a $q_1$ such that $|x-\sqrt{2}| \geq |x-q_1|$ for all small $x$, and another $q_1$ for large $x$. But one cannot find a $q_1$ that works for all $x$ at once.

Comment by Ewan Delanoy

2012-02-03T21:17:24Z

Your construction is essentially a local one - you can obtain a set of roots that work for all small $x$, and another that work for all large $x$. But those two constructions get into each other's way.

Comment by Ewan Delanoy

2012-02-03T19:13:58Z

I already thought of your idea, but unfortunately it does not work. The problem is that your construction will yield a case where (*) holds for "almost all" x (i.e. when $x$ is large enough), but not all x, and mathematicians do mind this ... Also, note that (*) does not hold when $P$ has an irrational root : e.g. if $P=(x-\sqrt{2})^2$, there is no $q_1$ such that $P \geq (x-q_1)^2$ for all $x$.

Comment by Ewan Delanoy

2011-10-31T11:08:54Z

@Douglas : you're absolutely right. Note that your family of examples is actually the convex hull between $h_{-1}$ and $h_1$, so perhaps looking at extremal elements inside those maximal elements yields a really finite set this time.

Comment by Ewan Delanoy

2011-09-15T18:02:28Z

@Francois : you're right, your trick still works in my updated version and I should have thought more before posting it on mathoverflow. As I found a new idea, I indulged in a breach of mathoverflow etiquette by erasing the old update's content and replacing it with a new content. Hopefully this new update will be more resistant to simple attacks.

Comment by Ewan Delanoy

2011-09-01T09:18:03Z

@Asaf : thanks for the suggestion. I'm still in the dark, however, as to why it is not a research-level question.

Comment by Ewan Delanoy

2011-09-01T06:51:51Z

I may be stupid but I have followed a course on computability, checked some sources including Manin's book on mathematical logic, and this is not a homework question. If someone could charitably explain in one sentence why this question is stupid, I'd gladly delete it.

Comment by Ewan Delanoy

2011-08-17T15:53:51Z

If $p$ and $q$ are both rational, the random walk is on $\frac{1}{n}.{\mathbb Z}$ for some $n$.

Comment by Ewan Delanoy

2011-08-16T05:12:05Z

@Douglas : I'm mainly interested in the case where both $p$ and $q$ are $<\frac{1}{2}$ (and $p$ and $q$ represent different gambling strategies).

Comment by Ewan Delanoy

2011-08-16T05:09:19Z

The Central Limit Theorem tells us that the distribution of ${S_n}^p$ converges to $N(0,1)$. In what sense can it be said that tends to Brownian motion? Where does the $C_p$ constant come from?

Comment by Ewan Delanoy

2011-06-02T18:18:41Z

-1 : There is no reason to rewrite as an "answer" what you already said in your comment.

Comment by Ewan Delanoy

2011-06-02T18:18:21Z

@Michael : Sorry for the unclear English in the OP. By "one" I mean "at least one", not "exactly one".