User ewan delanoy - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T15:57:11Z http://mathoverflow.net/feeds/user/2389 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19496/approximate-solutions-for-trisecting-the-angle-or-squaring-the-circle Approximate solutions for trisecting the angle or squaring the circle Ewan Delanoy 2010-03-27T09:27:30Z 2013-04-25T20:46:50Z <p>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 :</p> <p>Define explicitly a compasses-and-ruler only algorithm with the following properties :</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/87461/every-positive-polynomial-with-rational-coefficients-is-above-a-completely-q-fact Every positive polynomial with rational coefficients is above a completely Q-factorized nonnegative polynomial ? Ewan Delanoy 2012-02-03T18:05:51Z 2012-09-11T17:40:11Z <p>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.</p> <p>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> <p>$$(*) \ \ \ P(x) \geq \bigg( \prod_{k=1}^{d} (x-q_k)^2\bigg)$$</p> <p>for all $x\in \mathbb R$ ? </p> <p>I can show that the answer is YES when $d=1$ or $d=2$.</p> <p>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.</p> <p>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</p> <p>$$Q=X^2 + (a_3 + 2\eta_1)X + (a_2 + (2a_3\eta_1 + 3\eta_1^2))$$</p> <p>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> <p>$$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)$$</p> <p>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$$</p> <p>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.</p> http://mathoverflow.net/questions/28656/intuitive-and-or-philosophical-explanation-for-set-theory-paradoxes Intuitive and/or philosophical explanation for set theory paradoxes Ewan Delanoy 2010-06-18T19:08:53Z 2012-04-15T15:24:29Z <p>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$).</p> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/83229/quotients-of-perfect-powers-separated-by-an-integer Quotients of perfect powers separated by an integer Ewan Delanoy 2011-12-12T08:17:39Z 2011-12-12T16:21:59Z <p>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).</p> <p>My question is : is there always an integer between $a_n$ and $b_n$ ? This holds for $1 \leq n \leq 100$.</p> http://mathoverflow.net/questions/79603/one-sided-version-of-the-best-approximation-polynomial-upper-polynomial-appro One-sided version of the "best approximation polynomial" : Upper polynomial approximations Ewan Delanoy 2011-10-31T09:20:05Z 2011-10-31T11:06:02Z <p>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</p> <p>$$S=\lbrace h : X \to {\mathbb R} | h \geq f, \ h {\rm\ is \ the \ restriction \ of \ a \ polynomial \ } g {\rm \ of \ degree \ } d\rbrace$$</p> <p>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$ ?</p> <p>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). </p> <p>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.</p> http://mathoverflow.net/questions/78829/smallest-size-for-an-incomplete-tournament-with-property-s-k Smallest size for an incomplete tournament with property $S_k$ Ewan Delanoy 2011-10-22T13:45:02Z 2011-10-22T13:45:02Z <p>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). </p> <p>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$ ?</p> http://mathoverflow.net/questions/75088/mutually-incompatible-abstraction-terms mutually incompatible abstraction terms? Ewan Delanoy 2011-09-10T11:02:06Z 2011-09-15T17:53:02Z <p>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?</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/72946/comparing-hitting-probabilities-for-two-different-random-walks Comparing hitting probabilities for two different random walks Ewan Delanoy 2011-08-15T18:10:50Z 2011-08-15T21:21:49Z <p>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$.</p> <p>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)$ ?</p> http://mathoverflow.net/questions/66962/unknot-algebraic-set-defined-by-two-mutually-dependent-set-of-variables "Unknot" algebraic set defined by two mutually dependent set of variables Ewan Delanoy 2011-06-05T12:01:25Z 2011-06-05T19:47:31Z <p>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 </p> <p>$\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)$,</p> <p>where $\sigma_k$ denotes the $k$-th symmetric polynomial.</p> <p>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?</p> http://mathoverflow.net/questions/66738/is-there-a-good-explanation-for-this-fact-on-pairwise-independent-variables Is there a good explanation for this fact on pairwise independent variables? Ewan Delanoy 2011-06-02T14:26:19Z 2011-06-03T20:44:11Z <p>(related question : <a href="http://mathoverflow.net/questions/7998/most-general-way-to-generate-pairwise-independent-random-variables" rel="nofollow">http://mathoverflow.net/questions/7998/most-general-way-to-generate-pairwise-independent-random-variables</a>)</p> <p>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.</p> <p>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.</p> <p>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?</p> <p>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 $&lt;1$ (in this sense, $(X_3,X_4)$ cannot be "dependent" on $(X_1,X_2)$).</p> http://mathoverflow.net/questions/64973/sufficiently-random-sample Sufficiently random sample Ewan Delanoy 2011-05-14T09:12:35Z 2011-05-14T20:50:04Z <p>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 &lt; 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}$.</p> <p>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$.</p> <p>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?</p> http://mathoverflow.net/questions/61229/splitting-an-evaluated-complete-graph/61435#61435 Answer by Ewan Delanoy for Splitting an evaluated complete graph Ewan Delanoy 2011-04-12T17:55:05Z 2011-04-12T17:55:05Z <p>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.</p> <p>First, we need some notation : for $A \cup B$ a nontrivial partition of $V=\lbrace 1,2,3, \ldots ,7\rbrace$, let</p> <p>$$s(A,B)=\sum_{(x,y) \in A \times B} \omega(\{ x,y \}), \ f(A)=s(A,V\setminus A).$$</p> <p>We can now write some useful relations :</p> <p>$$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))$$</p> <p>(where, for simplicity, we write $f(i)$ instead of $f(\lbrace i \rbrace)$, $f(i,j)$ instead of $f(\lbrace i,j \rbrace)$, etc).</p> <p>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}$.</p> <p>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.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>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. </p> http://mathoverflow.net/questions/61199/complex-version-of-farkas-lemma Complex version of Farkas' lemma Ewan Delanoy 2011-04-10T09:32:22Z 2011-04-10T12:01:34Z <p>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$.</p> <p>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 <code>${\cal M}_{n,1}({\mathbb C})$</code> ) 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$.</p> <p>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</p> <p>$$\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.$$</p> http://mathoverflow.net/questions/60358/structure-of-nonaveraging-sets-of-integers Structure of nonaveraging sets of integers Ewan Delanoy 2011-04-02T12:55:05Z 2011-04-03T08:10:52Z <p>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. </p> <p>There is a regularly updated website on nonaveraging sets records at <a href="http://www.math.uni.wroc.pl/~jwr/non-ave/DATABASE.TXT" rel="nofollow">http://www.math.uni.wroc.pl/~jwr/non-ave/DATABASE.TXT</a>. 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.</p> <p>Despite the randomness, the optimal nonaveraging sets display some structure :</p> <p>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 :</p> <p>** 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)$.</p> <p>** 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)$.</p> <p>** 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)$.</p> <p>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$".</p> <p>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? </p> http://mathoverflow.net/questions/59956/consecutive-irreducible-polynomials "Consecutive" irreducible polynomials Ewan Delanoy 2011-03-29T07:07:02Z 2011-03-29T12:02:23Z <p>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)$ ?</p> http://mathoverflow.net/questions/59741/are-there-infinitely-many-triples-of-consecutive-square-free-integers are there infinitely many triples of consecutive square-free integers? Ewan Delanoy 2011-03-27T17:11:52Z 2011-03-28T10:32:10Z <p>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$). </p> <p>A related question : <a href="http://mathoverflow.net/questions/32412/question-on-consecutive-integers-with-similar-prime-factorizations" rel="nofollow">http://mathoverflow.net/questions/32412/question-on-consecutive-integers-with-similar-prime-factorizations</a></p> http://mathoverflow.net/questions/58961/best-rational-approximation-in-a-special-sense Best rational approximation in a special sense Ewan Delanoy 2011-03-20T10:45:30Z 2011-03-20T15:34:46Z <p>Let $\alpha$ be an irrational number, $n\geq 1$ and</p> <p>$X_n=\lbrace (x,y) \in {\mathbb Z}^2 | |y| \leq n, \ x+y\alpha >0 \rbrace$</p> <p>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.</p> <p>The two simplest cases are :</p> <p>$x_n=0,y_n=1$. This is equivalent to $0 &lt; \alpha &lt; \frac{1}{n+1}$.</p> <p>$x_n=1,y_n=-2$. This is equivalent to $\frac{1}{2}-\frac{1}{2m} &lt; \alpha &lt; \frac{1}{2}$ (where $m$ is the smallest odd integer $>n$).</p> <p>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)$ ?</p> <p>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.</p> http://mathoverflow.net/questions/58238/recurrence-equations-for-matrix-determinant/58246#58246 Answer by Ewan Delanoy for Recurrence Equations for Matrix Determinant Ewan Delanoy 2011-03-12T08:43:55Z 2011-03-12T08:43:55Z <p>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.</p> <p>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</p> <p>$$B_k=A^{k-1}+ \sum_{j=0}^{k-2}a_{n+1-k+j}A^j$$</p> <p>for all $k$. Finally, the Cayley-Hamilton theorem shows that $AB_n$ is exactly $-a_0I$. </p> http://mathoverflow.net/questions/17526/smallest-integer-not-divisible-by-integers-in-a-finite-set Smallest integer not divisible by integers in a finite set Ewan Delanoy 2010-03-08T21:23:03Z 2011-02-25T09:47:16Z <p>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)$.</p> <p>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$. </p> <p>Question 2 : If $\gamma$ is well-defined, are any asymptotics known about $\gamma(t)$ ?</p> http://mathoverflow.net/questions/54682/analogue-of-an-orthogonal-subspace-in-a-noneuclidian-normed-space Analogue of an orthogonal subspace in a noneuclidian normed space Ewan Delanoy 2011-02-07T18:46:48Z 2011-02-07T20:55:24Z <p>This question is related to <a href="http://mathoverflow.net/questions/50600/an-existence-question-on-linear-map" rel="nofollow">http://mathoverflow.net/questions/50600/an-existence-question-on-linear-map</a>. If the answer to this question is yes, it would solve the abovementioned other MO question.</p> <p>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. </p> http://mathoverflow.net/questions/48365/minimal-subset-of-axioms-for-zfc Minimal subset of axioms for ZFC Ewan Delanoy 2010-12-05T13:29:58Z 2011-02-07T18:26:12Z <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54337#54337 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}$? Ewan Delanoy 2011-02-04T17:41:16Z 2011-02-04T17:41:16Z <p>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 <code>$\cal P$</code> of primes such that the sequence <code>$(a_n)_{n\geq 1}$</code> satisifies some linear recurrence modulo <code>$p$</code> for every <code>$p\in {\cal P}$</code>.</p> <p>Now consider the function $A$ defined by <code>$A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$</code> for all <code>$n \geq 0$</code>. Let <code>$\Omega$</code> be the set of all integers $t\geq 1$ such that the vectors <code>$A(i+1),A(i+2), \ldots ,A(i+t)$</code> are linearly dependent over <code>$\mathbb Q$</code> for some $i$. Then <code>$r+1\in \Omega$</code> so <code>$\Omega$</code> is nonempty. Let $t$ be the smallest element in <code>$\Omega$</code> , and pick up $i$ such that <code>$A(i+1),A(i+2), \ldots ,A(i+t)$</code> are linearly dependent over $\mathbb Q$. By the choice of $t$, we have <code>$t \leq r+1$</code> and <code>$A(i+1),A(i+2), \ldots ,A(i+t-1)$</code> are linearly independent over $\mathbb Q$, so the last vector <code>$A(i+t)$</code> is a linear combination of <code>$A(i+1),A(i+2), \ldots ,A(i+t-1)$</code>:</p> <p><code>$$(*) : A(i+t)=\sum_{k=1}^{t-1} \beta_k A(i+k)$$</code></p> <p>for some coefficients <code>$\beta_1,\beta_2, \ldots ,\beta_k \in {\mathbb Q}$</code>. Now define a new sequence <code>$(b_n)_{n \geq i}$</code> by</p> <p><code>$$b_n=a_{n+t}-\sum_{k=1}^{t-1} \beta_k a_{n+k}$$</code></p> <p>By (*) above, the first $r$ values of <code>$(b_n)_{n \geq 1}$</code> are $0$ (in $\mathbb Q$). Now for <code>$p\in {\cal P}$</code>, the sequence <code>$(b_n \ ({\rm mod} \ p))_{n \geq i}$</code> satisifies a linear recurrence of order $r$, ans starts with $r$ zeroes. So that sequence is identically zero. We deduce that $p$ divides <code>$b_n$</code> for any <code>$p\in {\cal P}$</code> and <code>$n \geq i$</code>, so that <code>$(b_n)_{n \geq i}$</code> is identically $0$ in $\mathbb Q$. </p> <p>So we see that $(*)$ still holds when $i$ is replaced by any <code>$n\geq i$</code>, and that the initial sequence <code>$(a_n)_{n\geq 1}$</code> eventually satisfies a linear recurrence of degree <code>$\leq r$</code>.</p> http://mathoverflow.net/questions/54315/can-an-integer-or-rational-sequence-satisfy-some-bounded-order-recurrence-mod/54323#54323 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}$? Ewan Delanoy 2011-02-04T15:46:02Z 2011-02-04T15:56:12Z <p>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 <code>$p\in {\cal P}$</code> there is a function <code>$f_p$</code> from <code>${\mathbb Z}_p^r$</code> to <code>${\mathbb Z}_p$</code> such that the sequence <code>$(a_n)_{n\geq 1}$</code> satisfies <code>$$a_{n+r+1} \equiv f_p(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r}) \ ({\rm mod} \ p)$$</code> for all <code>$n\geq 0$</code> and <code>$p\in {\cal P}$</code>.</p> <p>Now consider the function $A$ defined by <code>$A(n)=(a_{n+1},a_{n+2},a_{n+3}, \ldots ,a_{n+r})$</code> for all <code>$n \geq 0$</code>. If <code>$A$</code> is injective, the sequence <code>$(a_n)_{n\geq 1}$</code> satisfies a recurrence of degree <code>$r$</code> in <code>$\mathbb Q$</code>. If <code>$A$</code> is not injective, then there are integers <code>$i \lt j$</code> such that <code>$A(i)=A(j)$</code>. Then the values <code>$a_{i+r+1}$</code> and <code>$a_{j+r+1}$</code> agree modulo all primes in $\cal P$, and are therefore equal in $\mathbb Q$. By induction, we see that the sequence <code>$(a_n)_{n\geq 1}$</code> is eventually <code>$(j-i)$</code>-periodic. Then a (more delicate) construction shows that <code>$(a_n)_{n\geq 1}$</code> still satisfies a recurrence of degree <code>$r$</code> in <code>$\mathbb Q$</code></p> http://mathoverflow.net/questions/53610/which-polynomials-arise-as-formulas-for-a-conjugate Which polynomials arise as formulas for a conjugate Ewan Delanoy 2011-01-28T12:23:24Z 2011-01-29T07:42:04Z <p>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$ ?</p> http://mathoverflow.net/questions/17162/strengthening-of-dirichlets-theorem-on-arithmetic-progressions Strengthening of Dirichlet's theorem on arithmetic progressions Ewan Delanoy 2010-03-05T05:52:30Z 2011-01-21T14:22:06Z <p>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. </p> <p>I am wondering if the following strengthening of Dirichlet's theorem is also true : </p> <p>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). </p> <p>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.</p> <p>Perhaps the two are in fact equivalent ?</p> http://mathoverflow.net/questions/51100/simplest-examples-of-unique-solution-and-unsolvable-without-backtracking-sudoku-l Simplest examples of unique-solution and unsolvable-without-backtracking Sudoku-like problems Ewan Delanoy 2011-01-04T09:38:29Z 2011-01-04T18:06:57Z <p>A</p> <p>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$.</p> <p>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$.</p> <p>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)$). </p> <p>Perfect irreducible Sudoku-like problems do exist (the ordinary Sudoku problem in the end of David Eppstein's arXiv paper <a href="http://arxiv.org/abs/cs/0507053v1" rel="nofollow">http://arxiv.org/abs/cs/0507053v1</a> 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$ ?</p> http://mathoverflow.net/questions/50831/example-just-slightly-better-than-the-greedy-construction example just slightly better than the greedy construction Ewan Delanoy 2010-12-31T21:23:04Z 2011-01-02T17:55:03Z <p>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).</p> <p>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 <a href="http://gilkalai.wordpress.com/2008/07/10/pushing-behrend-around/" rel="nofollow">http://gilkalai.wordpress.com/2008/07/10/pushing-behrend-around/</a>). 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.</p> <p>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 :</p> <p>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 | &lt; |T \cap \lbrace 1,2, \ldots ,n \rbrace |$ for all large enough $n$ ?</p> <p>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. </p> http://mathoverflow.net/questions/49365/does-every-symmetric-group-s-n-have-a-single-element-of-maximal-word-norm/49370#49370 Answer by Ewan Delanoy for Does every symmetric group S_n have a single element of maximal word norm? Ewan Delanoy 2010-12-14T08:48:36Z 2010-12-14T08:48:36Z <p>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)$$. </p> <p>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$.</p> <p>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)$.</p> <p>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}$.</p> http://mathoverflow.net/questions/47458/cantors-argument-revisited/47576#47576 Answer by Ewan Delanoy for Cantor's argument revisited Ewan Delanoy 2010-11-28T09:52:34Z 2010-11-28T16:06:37Z <p>If I understood the OP correctly, the problem can be stated as follows :</p> <p><strong>Problem 1.</strong> Let $X$ be a set, let <code>$F:{\cal P}(X) \to X$</code>, and let $A$ be defined as above: <code>$$A=\lbrace F(Z) | Z\subseteq X, F(Z) \not\in Z\rbrace.$$</code> Find a definable $B$ (in terms of $F$) such that $B \neq A$ and $F(B)=F(A)$.</p> <p>Now Problem 1 is equivalent to the simpler problem :</p> <p><strong>Problem 2.</strong> 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'$.</p> <p>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 <code>$W=\lbrace w_k \rbrace_{k \geq 0}$</code> 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:</p> <ol> <li><code>$F(\lbrace (y,w_0) \rbrace)=a$</code>, if <code>$y\in {Y'}$</code>,</li> <li><code>$F(\lbrace (y,w_{k+1}) \rbrace)=(y,w_k)$</code> , for all $y\in Y$ and <code>$k\ge0$</code>,</li> <li><code>$F(X)=a$</code>, and </li> <li><code>$F(Z)=b$</code> for all other subsets $Z$ of $X$ (thus $F(\emptyset)=b$).</li> </ol> <p>Now, by construction, $A=X$, and any solution $B$ to Problem 1 is of the form <code>$\lbrace (y,w_0) \rbrace$</code> for some $y\in Y'$, thereby solving Problem 2.</p> http://mathoverflow.net/questions/46262/finite-interpolation-by-nondecreasing-indefinitely-differentiable-functions-in-a Finite interpolation by nondecreasing indefinitely differentiable functions in a finite-dimensional space Ewan Delanoy 2010-11-16T17:11:48Z 2010-11-17T04:15:45Z <p>Some time ago, I asked about inite interpolation by a nondecreasing polynomial here at <a href="http://mathoverflow.net/questions/16673/finite-interpolation-by-a-nondecreasing-polynomial" rel="nofollow">http://mathoverflow.net/questions/16673/finite-interpolation-by-a-nondecreasing-polynomial</a>. 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.</p> <p>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?</p> <p>Formally, fix <code>$x_1 \lt x_2 \lt \ldots \lt x_n$</code> and let <code>$y_1 \leq y_2\leq \ldots \leq y_n$</code> vary. We consider the system $(S)$ made of the $n$ interpolation constraints <code>$f(x_i)=y_i$</code> for $i$ between $1$ and $n$. Is there a finite-dimensional subspace $V$ of <code>${\cal C}^{\infty}([x_1,x_n],{\mathbb R})$</code> such that for any <code>$y_1 \leq y_2\leq \ldots \leq y_n$</code>, there is a solution to $(S)$ which is nondecreasing and also in $V$?</p> http://mathoverflow.net/questions/28656/intuitive-and-or-philosophical-explanation-for-set-theory-paradoxes/94100#94100 Comment by Ewan Delanoy Ewan Delanoy 2012-04-22T14:39:21Z 2012-04-22T14:39:21Z Interesting. &quot;Empty&quot; is not the same thing as &quot;vicious&quot; indeed. http://mathoverflow.net/questions/87461/every-positive-polynomial-with-rational-coefficients-is-above-a-completely-q-fact/87466#87466 Comment by Ewan Delanoy Ewan Delanoy 2012-02-04T16:17:58Z 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. http://mathoverflow.net/questions/87461/every-positive-polynomial-with-rational-coefficients-is-above-a-completely-q-fact/87466#87466 Comment by Ewan Delanoy Ewan Delanoy 2012-02-04T16:16:51Z 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 &quot;uniformity&quot; 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. http://mathoverflow.net/questions/87461/every-positive-polynomial-with-rational-coefficients-is-above-a-completely-q-fact/87466#87466 Comment by Ewan Delanoy Ewan Delanoy 2012-02-03T21:19:54Z 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. http://mathoverflow.net/questions/87461/every-positive-polynomial-with-rational-coefficients-is-above-a-completely-q-fact/87466#87466 Comment by Ewan Delanoy Ewan Delanoy 2012-02-03T21:17:24Z 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. http://mathoverflow.net/questions/87461/every-positive-polynomial-with-rational-coefficients-is-above-a-completely-q-fact/87466#87466 Comment by Ewan Delanoy Ewan Delanoy 2012-02-03T19:13:58Z 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 &quot;almost all&quot; 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$. http://mathoverflow.net/questions/79603/one-sided-version-of-the-best-approximation-polynomial-upper-polynomial-appro Comment by Ewan Delanoy Ewan Delanoy 2011-10-31T11:08:54Z 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. http://mathoverflow.net/questions/75088/mutually-incompatible-abstraction-terms Comment by Ewan Delanoy Ewan Delanoy 2011-09-15T18:02:28Z 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. http://mathoverflow.net/questions/74226/is-the-set-of-all-deducible-formulas-decidable Comment by Ewan Delanoy Ewan Delanoy 2011-09-01T09:18:03Z 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. http://mathoverflow.net/questions/74226/is-the-set-of-all-deducible-formulas-decidable Comment by Ewan Delanoy Ewan Delanoy 2011-09-01T06:51:51Z 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. http://mathoverflow.net/questions/72946/comparing-hitting-probabilities-for-two-different-random-walks Comment by Ewan Delanoy Ewan Delanoy 2011-08-17T15:53:51Z 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$. http://mathoverflow.net/questions/72946/comparing-hitting-probabilities-for-two-different-random-walks Comment by Ewan Delanoy Ewan Delanoy 2011-08-16T05:12:05Z 2011-08-16T05:12:05Z @Douglas : I'm mainly interested in the case where both $p$ and $q$ are $&lt;\frac{1}{2}$ (and $p$ and $q$ represent different gambling strategies). http://mathoverflow.net/questions/72946/comparing-hitting-probabilities-for-two-different-random-walks/72954#72954 Comment by Ewan Delanoy Ewan Delanoy 2011-08-16T05:09:19Z 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? http://mathoverflow.net/questions/66738/is-there-a-good-explanation-for-this-fact-on-pairwise-independent-variables/66758#66758 Comment by Ewan Delanoy Ewan Delanoy 2011-06-02T18:18:41Z 2011-06-02T18:18:41Z -1 : There is no reason to rewrite as an &quot;answer&quot; what you already said in your comment. http://mathoverflow.net/questions/66738/is-there-a-good-explanation-for-this-fact-on-pairwise-independent-variables Comment by Ewan Delanoy Ewan Delanoy 2011-06-02T18:18:21Z 2011-06-02T18:18:21Z @Michael : Sorry for the unclear English in the OP. By &quot;one&quot; I mean &quot;at least one&quot;, not &quot;exactly one&quot;.