User sjr - MathOverflow

Answer by SJR for Computing the Galois group of a polynomial

2010-04-29T06:01:41Z

There is an algorithm described in an ancient and interesting book on Galois Theory by Eugene Dickson. Here is a brief sketch in the case of an irreducible polynomial $f\in \mathbb{Q}[x]$.

Suppose that $z_1\ldots z_n$ are the roots of $f$ in some splitting field of $f$ over $\mathbb{Q}$. (We don't need to construct the splitting field. The $z_i$ are mentioned here for the sake of explanation.) Let $x_1\ldots x_n$ be indeterminates. For a permutation $\sigma\in S_n$, let $$E_\sigma=x_1z_{\sigma(1)}+\ldots+ x_n z_{\sigma(n)}.$$ Let $g(x):=\prod _{\sigma} (x-E_\sigma)$ , where $\sigma$ runs through all permutations in $S_n$. Each coefficient $c_i$ of $x^i$ in $g$ is symmetric in $z_1 \ldots z_n$, so (using the theorem on symmetric functions) we can write $c_i$ as a polynomial in $x_1\dots x_n$ with rational coefficients.

Assuming that this has been done, factor $g$ into irreducibles over the ring $\mathbb{Q}[x_1 \ldots x_n]$. Let $g_0$ be the irreducible factor of $g$ that is satisfied by $E_{Id}$, where $Id$ is the identity permuation. Then the galois group of $f$ consists of all permutations of $x_1\ldots x_n$ that fix $g_0$.

The point is that the computation of $g_0$ is effective (albeit horrendous) and so is the determination of the permutations that fix $g_0$.

Answer by SJR for First order decidability of rings vs Diophantine decidability

2013-05-08T15:17:57Z

Let $F=\mathbb{R}(t)$ be the field of rational functions in the variable $t$ with real coefficients. We regard $F$ as a structure of type $(+ \times -\,\, 0\,\, 1)$ . Then

The (positive) existential theory of $F$ is effectively computable (e.c.)
The full first-order theory of $F$ is not e.c.

Proof of 1: Suppose that a system of polynomial equations has a solution $\bar{r}$ in $F$. Here $\bar{r}$ is a tuple of rational functions. Choose a real number $s$ that is not a root of any of the denominators of the rational functions $r_i$ and substitute $s$ for $t$ in $\bar{r}$, to obtain a tuple of real numbers that satisfies the same system of equations. Conversely, a tuple of reals that satisfies a given system of equations is already a tuple of rational functions. It follows that the existential theory of $F$ is e.c. if and only if the existential theory of $\mathbb{R}$ is e.c. But the last statement is true, by a well-known theorem of Tarski.

Proof of 2: A proof of the undecidablity of the first-order theory of $F$ (actually $\mathbb{R}$ can be replaced by any archimedian formally real field) is the subject of a 1961 paper by Raphael Robinson here. Especially, look at Section 3, "The Method of Julia Robinson." The argument shows (amazingly) that the natural numbers can be defined in $F$.

Zeros of polynomials in discretely ordered rings

2013-04-23T14:08:10Z

Let's say that a discretely ordered ring has rank 1 if it has elements greater than any integer, and for any two such elements $x<y$ there is an integer $n$ such that $x^n>y$ .

Question: Let $f(\bar{x})$ be a polynomial in any number of variables with integer coefficients that has a zero in at least one discretely ordered ring. Must $f$ have a zero in a discretely ordered ring of rank 1?

Answer by SJR for References on techniques for solving equations with discontinuous functions such as floor and ceiling?

2013-04-16T12:51:34Z

Expressions formed by composing polynomials and the integer-part operator are refered to in numerous papers by the not very google-friendly name ``generalized polynomials''. The problem of determining whether a generalized polynomial equation has integer solutions includes Hilbert's Tenth problem, and is therefore effectively unsolvable. On the other hand there are some interesting results on the distribution of values of generalized polynomials, which you might find relevant:

Bergelson and Leibman's paper ``Distribution of values of bounded generalized polynomials'' available here.
Leibman's paper ``A canonical form and the distribution of values of generalized polynomials'' available here.

There are related papers on Leibman's website and also by Haland and McCutcheon. Leibman's paper gives a cannonical form for generalized polynomials that helps to grasp what values the gp can assume mod 1. His paper is a follow-up to the Bergelson-Leibman paper, in which Bergelson shows very roughly speaking that every bounded generalized polynomial can be thought of as a matrix power map composed with a piecewise-polynomial function. Bergelson shows how tools from Ergodic Theory and Lie Theory can be brough to bear on the study of generalized polynomials.

Incidentally, the problem of which equations $g=0$ are identities (i.e. hold for all integer values of the variables), where g is a gp, is also effective unsolvable by reduction to Hilbert's Tenth Problem: Let $f$ be any polynomial with integer coefficients. Then the equation $$\lfloor \sqrt{2}f(\bar{x})\rfloor+\lfloor- \sqrt{2}f(\bar{x})\rfloor+1=0$$ is an identity if and only if $f$ has no integer zeros.

Computing the measure of the projection on the torus of a semialgebraic set

2012-07-01T06:25:23Z

Let $V \subseteq \mathbb{R}^n$ be a set cut out by a system of finitely many polynomial equations and inequalities with integer coefficients. Let $W$ be the set of all points in the box $[0,1]^n$ that are congruent mod 1 to some point of $V$. I would like to know whether or not there is an algorithm for determining if a given rational number is equal to, greater than or less than the Lebesgue measure of $W$. There may not be one, in light of this argument, which proves, in effect, that there is no algorithm to determine if $W=[0,1]^n$.

Note that one can effectively produce arbitrarily accurate lower bounds on the measure of $W$, by breaking up $V$ into small pieces and translating more and more of these pieces to $[0,1]^n$. The problem is, I don't see how to get arbitrarily accurate upper bounds on the measure of $W$.

Answer by SJR for Sets of integers represented by degree zero rational functions

2013-01-29T06:45:20Z

A set $T \subseteq \mathbb{Z}$ can be written as $S(f)$ if and only if $T$ is effectively enumerable.

Proof: As in zeb's comment, the restriction to degree zero doesn't matter, and we consider rational functions of arbitrary degree.

Suppose $T$ is effectively enumerable. By the MRDP theorem choose a polynomial $f(\bar{z},x)$ such that $T$ is precisely all $x$ for which the equation $f(\bar{z},x)=0$ is solvable in integers $\bar{z}$. Then the rational function \begin{equation*} r(\bar{z},x):=x+\dfrac{f(\bar{z},x)^2}{1+f(\bar{z},x)^2} \end{equation*} has the value $x$ if $f(\bar{z},x)=0$, and otherwise is not an integer. Therefore $T=S(r)$.

Conversely, it is intuitively clear that every set of the form $S(r)$, with $r$ a rational function, is effectively enumerable.

Answer by SJR for Are there ever exotic isomorphisms between quotients of F[x]?

2012-10-12T08:24:17Z

The answer is yes, if $\phi$ is an isomorphism of rings:

Take $F$ to be the reals, and let $I$ and $J$ both be the ideal of $F[x]$ generated by $x^2+1$. Let $q=q_i=q_j$ be the projection map. The quotient $E:=q(F)$ is isomorphic to the complex numbers. Let $\phi$ be any automorphism of $E$ taking $2^{1/4}$ to $2^{1/4}i$, where $2^{1/4}$ is a real fourth root of 2 and $i$ is $q(x)$.

If $\psi$ is any endomorphism of $F[x]$ then $$q(\psi(2^{1/4}))=q(\pm2^{1/4})=\pm2^{1/4},$$ whereas $$\phi(q(2^{1/4}))=\phi(2^{1/4})=2^{1/4}i.$$ Thus $q\circ\psi\ne\phi\circ q$.

The first equation follows from the fact that $\psi$ preserves $\mathbb{Q}$-conjugates, and also $\psi$ must map $F$ into $F$ because $\psi$ preserves units.

Estimating the volume of a semialgebraic set from above

2012-09-11T00:44:30Z

Suppose $S$ is a subset of $\mathbb{R}^n$ of finite volume defined by a system of finitely many polynomial inequalities with integer coefficients. Can anyone describe an algorithm that, given such a system of inequalities, generates a sequence of rational numbers that converges to the volume of $S$ from above?

This question expands a comment of Andrej Bauer to a related question.

This question was posted on math stackexchange here. There were no responses.

The case that baffles me is when $S$ is unbounded. The obvious approach would be to find some general way to enlarge $S$ by "a little bit" to a set whose volume is easy to compute. But I don't see how to do this.

Actually, I cannot even describe an algorithm to determine whether or not $S$ has finite volume, and such an algorithm might give a good start to solving the original problem

Discrete orderings on polynomial rings that violate the universal theory of the integers

2012-09-20T12:16:08Z

Working in the language of ordered rings, which we take to have type $(+ - \times < 0\, 1)$ , can anyone give an example of a discrete ordering on the polynomial ring in two variables $\mathbb{Z}[x,y]$ such that the resulting ordered ring does not satisfy the universal theory of the integers?

It is not difficult to show that as a ring, i.e. forgetting the less-than symbol, the ring $\mathbb{Z}[x,y]$ does in fact satisfy the universal theory of the ring of integers. The problem is to find a discrete ordering on $\mathbb{Z}[x,y]$ such that some system of inequalities is solvable in $\mathbb{Z}[x,y]$ but not in the integers, or, on the contrary, to prove that there is no such ordering.

Is the first order theory of ordered rings without infinitesimals effectively enumerable?

2012-09-05T13:03:46Z

We take an ordered ring to be a structure of type $(+ - \times < 0\,\, 1)$ satisfying the usual axioms. If $A$ is an ordered ring then we say that an element $a$ of $A$ is infinitesimal if for all integers $n$ it holds that $-1<na<1$ .

Let $T$ be the set of sentences that hold in every ordered ring that has no infinitesimal elements other than 0.

Question: Is $T$ effectively enumerable? Is the set of universal sentences of $T$ effectively enumerable?

Answer by SJR for Fiction books about mathematicians?

2012-07-08T12:27:05Z

The Man Without Qualities (Der Mann ohne Eigenschaften) by Robert Musil. The protagonist is a Mathematician, and the book runs through an amazing range of issues concerning science, technology and their relations to society and to the nature of consciousness. It is set in the last days of the Austro-Hungarian Empire. The novel was never finished -- the published fragment runs to around 1700 pages.

Is the closure of a semialgebraic set mod 1 also semialgebraic?

2012-02-03T09:24:59Z

Let $p:\mathbb{R}^n\to[0,1)^n$ be the map defined by $p(x_1,\ldots,x_n)=(\{x_1\},\ldots,\{x_n\})$ , where $\{\cdot\}$ is the fractional part operator. Experimentation suggests that if $S \subseteq \mathbb{R}^n$ is semialgebraic, then the closure of the image set $p(S)$ is semialgebraic. (By a "semialgebraic" subset of $\mathbb{R}^n$ I mean here a finite union of sets, each defined by a system of polynomial inequalities with real coefficients. By "closure" I mean in the usual topology on $\mathbb{R}^n$, restricted to $[0,1)^n$.)

Is this true? Can anyone provide a proof or a counterexample or a relevant reference?

Answer by SJR for Solving a system of equations/inequalities that have trigonometric functions on the left-hand side

2012-01-27T18:47:22Z

Using, e.g., the sin function, one can write a system of inequalities in a given variable $x$ that is satisfied if and only if $x$ is an integer. Therefore, an algorithm for solving inequalities of the kind you asked about would give an algorithm of finding all integer solutions to an arbitrary system of inequalities. This would contradict the negative solution to Hilbert's Tenth Problem. See http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem

A question about the additive group of a finitely generated integral domain

2011-10-10T02:57:02Z

Let $R$ be an integral domain of characteristic 0 finitely generated as a ring over $\mathbb{Z}$. Can the quotient group $(R,+)/(\mathbb{Z},+)$ contain a divisible element? By a "divisible element" I mean an element $e\ne 0$ such that for every positive integer $n$ there is an element f such that $e=nf$.

As Darji points out, another way to ask the question is this: Suppose $e\in R$ has the property that for all positive integers $n$, $e$ is congruent to an integer mod $nR$. Must $e$ be an integer?

Note: I previously posted this to Math StackExchange here: http://math.stackexchange.com/questions/71031/a-question-about-the-additive-group-of-a-finitely-generated-integral-domain

TO SUMMARIZE: Qing Liu showed that in fact any non-integer rational in $R$ determines a divisible element of $(R,+)/(\mathbb{Z},+)$, and Wilberd van der Kallen showed that all divisible elements arise in this way. I wish I could accept both answers.

Answer by SJR for Searching for an inhomogeneous diophantine approximation algorithm

2011-07-12T17:00:09Z

The question can be clarified a bit. The difficulty has nothing to do with the existence of algorithms: The required coprime integers $a$ and $b$ can be found by a systematic search if they exist at all, assuming any reasonable interpretation of the word Given in the first sentence of the question.

Furthermore, it will simplify matters to divide the inequality in the first sentence by $x$.

With this in mind, I'll give a proof of the following assertion:

Let $\epsilon>0$. Suppose $a$ is irrational and $b$ is any real number. Then there are coprime integers $x$ and $y$ such that $|ax-y-b|<\epsilon$.

Proof: The proof has undergone a major rewrite, thanks to Gerry Myerson's helpful comments. The argument extends a similar result (not mentioning coprimality) proved in Khinchin's book on continued fractions, which is a good reference for the basic facts I'll use here.

Let $p/q$ be a convergent (to be specified later) of the continued fraction expansion of $a$. Then it is well known (see Khinchin) that $p$ and $q$ are coprime, and moreover that $|a-p/q|<1/q^2$.

The latter inequality implies that for some real number $\delta$ with $|\delta|<1$,

$$a=\frac{p}{q}+\frac{\delta}{q^2}.$$

We will now produce a peculiar-looking estimate for $b$, the reason for which will become apparent shortly. Note that without loss of generality we can and will take $b$ to be positive.

Let $t$ be the largest prime not larger than $bq$. Then by Bertrand's Postulate $t\le bq<2t$ . From this we deduce the following chain of inequalities: $$t/q\le b<2t/q\le t/q+b.$$ It follows that for some $\gamma$ with $0\le \gamma <b$ , $$b=\frac{t}{q}+\frac{\gamma}{q}.$$

Thus, for any integers $x$ and $y$, we have the equality $$|ax-y-b|=\left|\left(\frac{p}{q}+\frac{\delta}{q^2}\right)x-y-\left(\frac{t}{q}+\frac{\gamma}{q}\right)\right|.$$

The right hand side can be rewritten as $$\left|\frac{px-t}{q}-y +\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|,$$ and the latter is at most $$\left|\frac{px-t}{q}-y\right| +\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|.$$

Therefore to complete the proof it is enough to choose $q, x, y$ such that

(1) $x$ and $y$ are coprime.

(2) $\displaystyle\frac{px-t}{q}-y=0$, or equivalently $px-qy=t$.

(3) $\displaystyle\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|<\epsilon$.

Now since $p$ and $q$ are coprime, the equation $px-qy=t$ has integer solutions, say $x=x_0$ and $y=y_0$. For every integer $z$ there are additional solutions $x=x_0+qz$ and $y=y_0+pz$. Therefore we can choose solutions $x_0,\,y_0$ with $x_0$ in the interval $[0,q)$.

If $x_0$ and $y_0$ are not relatively prime, then since $px_0+qy_0=t$, and since $t$ is prime, it follows that $t$ is the only possible common factor. But if $t$ is in fact a common factor, then $x_0+q$ and $y_0+p$ must be relatively prime, because $t$ is likewise the only possible common factor of $x_0+q$ and $y_0+p$: But $t$ cannot divide these two integers lest $t$ divide both $p$ and $q$.

It follows that for any convergent $p/q$ for the continued fraction expansion of $a$, there are coprime integer solutions $x,\,y$ of the equation $px-qy=t$, with $x$ in the interval $[0,2q)$. For any such $x$, we have $$\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|<\frac{2}{q}+\frac{b}{q}.$$

Therefore, finally, if we choose $q$ so large that $\frac{2}{q}+\frac{b}{q}<\epsilon$, then Conditions (1) (2) and (3) are satisfied, and the proof is complete.

Efficient computation of the least fraction with square denominator greater than the square root of 2.

2011-05-17T11:40:04Z

The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a program that finds, in hours rather than centuries, the least rational greater than $\sqrt{2}$ of the form $x/y^2$ with $y^2\le 10^{100}$ ?

More generally, my question is whether the following computation is known to be feasible or not feasible:

Given $N$ , find the least rational greater than $\sqrt{2}$ of the form $x/y^2$, with $x$ and $y$ integers and $y^2\le N$. For definiteness, let's say that the output should be the required rational written in lowest form.

By a feasible computation I mean one that can be done in $O((\log N)^k)$ bit operations for some constant $k$.

Of course the square root of 2 is not essential here. Any irrational would do, as long as comparisons with rationals are feasible. I don't know of any such irrational for which I can answer the question I've posed.

Answer by SJR for Bounds on squarefree numbers

2011-06-02T06:34:33Z

The "Handbook of Number Theory" by Sandor, Mitrinovic and Crstici, page 201 gives $Q(x)\ge 53x/88$ , where $Q(x)$ is the number of square free positive integers less than or equal to $x$. This implies $q_n\le 88n/53$ . They cite "The Schnirelmann Density of the Squarefree Integers", K. Rogers, Proc. Am. Math. Soc. 15, 1964

Answer by SJR for Why can Diophantine equations represent exponential growth?

2011-05-31T04:31:35Z

A simple candidate for a diophantine relation exhibiting exponential growth is the relation between $x$ and $t$ in the equation $x^2-ty^2=1$ . According to Barry Mazur ("Questions of Decidability and Undecidability in Number Theory", JSL v59, 1994), the relation $$\phi(t,x):\exists y\,\,\, x^2-ty^2=1$$ exhibits exponential growth if Gauss's class number conjecture is true, i.e. if there are infinitely many real quadratic fields of class number 1.

Many years before the MRDP theorem was proved, Martin Davis and Julia Robinson boiled down Hilbert's Tenth Problem to the question of the existence of a diophantine relation of exponential growth. See Julia Robinson's 1950 paper "Existential Definability in Arithmetic".

[Added]

A caveat emptor is appropriate here, as I realized after responding to GH's comment. Julia Robinson shows in her paper that the relation $z=x^y$ is diophantine if there is a diophantine relation $\rho \subseteq\mathbb{N}\times \mathbb{N}$ satisfying

For no positive integer n is it true that $\forall x,y\in \mathbb{N}\,\, \rho(x,y)\to y<x^n$ , and
There is an exponential tower $t$ such that $\forall x,y\in \mathbb{N}\,\, \rho(x,y)\to y<t(x)$ , where an "exponential tower" is a function of the form $x^{x^{\ldots}}$.

Now Mazur's formula provides a (conditional) example of exponential growth in the sense of Julia Robinson's Condition (1), but violates Condition (2), because for a given $t$ there can be infinitely many pairs $x,y$ such that $x^2-ty^2=1$. (For example, when $t$ is square-free and greater than 1.)

This leads to a question that intrigues me: Is there some reasonably simple way to add some polynomial equations and inequalities (in any number of variables) to the equation $x^2-ty^2=1$ that forces the pairs $x,t$ in the equation $x^2-ty^2=1$ to satisfy Julia Robinson's Condition (2)? The result would be a quick proof of MRDP from the class number conjecture.

Incidentally, Mazur does mention that by a theorem of Hua, the least $x$ for which there is some $y$ such that $x^2-ty^2=1$ is bounded by an exponential tower in $t$.

Answer by SJR for Non-standard models of finite set theory

2011-05-04T08:44:00Z

Any positive integer can be written uniquely as a sum of distinct powers of 2. PA knows this, in the sense that one can write down a formula $\phi(x,y)$ meaning in the standard model that the $x$-th bit in the binary expansion of $y$ is 1. Moreover we can construct $\phi$ so that PA will prove all the expected facts about the $x$-th bit in the binary expansion of $y$.

If $M$ is any model of PA, then by taking $\phi(x,y)$ as the membership relation "$x\in y$" we get a model of ZF-Inf. This is worked out in detail in Chapter 1 of "Metamathematics of First Order Arithmetic" by Hajek and Pudlak. In fact the authors carry this out not just for PA but for the subtheory $\text{I}\Sigma_0(\text{exp})$ .

(Added) I expected that every model $M$ of ZF-Inf would arise in this way, by applying the above construction to the model of PA consisting of the ordinals of $M$. But it seems this is not so... See Ali's answer below.

Answer by SJR for What is the high-concept explanation on why real numbers are useful in number theory?

2011-04-14T08:14:53Z

The question seems to assume or at least sympathise with something along the lines of

     God created the integers and the reals are derived therefrom.

On the contrary, it seems just as plausible that the reals are our basic intuitive data. Meaning what?

In the history of cognition, measuring precedes counting. For example a lion can measure the length of his leap more easily than he can distinguish between 29 and 39 wildebeests.
The reals are the only Dedekind complete ordered field, if "cut" is taken in a set-theoretically naive way. See e.g., "Completeness of Ordered Fields" by Hall on arxiv. The integers are the unique discretely ordered subring of the reals. The induction principle for the ring of integers (and the uniqueness of the one and only discretely ordered subring of the reals) is a consequence of the completeness of the reals: An inductive set of integers that missed some positive integer would give rise to a cut with no boundaries. The notion of continuum, in other words, can be taken as the big defining concept here, and the main underlying intuition.
Number Theory, or at least Diophantine Analysis, can be understood as the study of equations over the reals with solutions restricted to certain subrings. Does the question "What are the reals doing in number theory" then dissolve? Maybe.

A question about how polynomials simplify under substitution

2011-01-24T14:38:26Z

This is a revised and more sensible version of the original question, thanks to the kind help of Anthony Quas and J. C. Ottem.

Fix polynomials $f_{1},\ldots, f_{n} \in \mathbb{C}[t]$. Let $M_{k}$ be the set of polynomials $h\in \mathbb{Z}[x_{1},\ldots,x_{n}]$ such that the $t$-degree of $h(f_{1}(t),\ldots f_{n}(t))$ does not exceed $k$. Under addition $M_{k}$ is an abelian group. Questions:

Suppose that $M_0$ contains only constant polynomials. Must $M_k$ be finitely generated for all $k$?
If the answer to Question 1 is YES (which is my guess) then can anyone explain how to calculate, given $k$ and the $f_i$, an upper bound on the total degrees of the polynomials in $M_k$?

Remark: The requirement that $M_0$ contain only constant polynomials is clearly necessary if $M_k$ is to be finitely generated for all $k$, since if $h$ is a non-constant polynomial in $M_0$ then $h^2$, $h^3$, etc. are all in $M_0$.

Remark: The word GIVEN in Question 2 may seem troublesome since the $f_i$ have arbitrary complex coefficients, but actually this is not a problem. If $c_1, c_2,\ldots$ are all the coefficients of all the polynomials $f_i$, then all we need to know to calculate the $t$-degrees of compositions of the form $h(f_{1}(t),\ldots f_{n}(t))$ are all polynomial relations among the $c_i$. All such relations can be specified by giving a finite basis for the vanishing ideal of $c_1, c_2,\ldots$ in the polynomial ring $\mathbb{Q}[x_1,x_2,\ldots]$.

Example: Let $r$ be a transcendental, let $c=\sqrt{2}$, and let $f_1, f_2= t, ct+r$. It is simple to check that $M_0$ contains only constant polynomials. Note that $M_1$ contains, in addition to $x_1$ and $x_2$, the polynomial $2x_1^2-x_2^2$, and I suspect that these three polynomials and 1 generate $M_1$. Can anyone prove even in this case, that each of the $M_k$ are finitely generated?

A question about open induction

2010-05-06T23:35:37Z

An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction if and only if for all $n>1$, there is a homomorphism from $R$ onto $\mathbb{Z}/n\mathbb{Z}$.

Wilkie's proof proceeds by adjoining transcendental elements to $R$, but it is not clear that this is ever necessary:

Does every ring that extends to a model of open induction have an algebraic extension to a model of open induction?

Does anyone know anything about this? I know of no place in the literature where the question is even mentioned, although it has come up more than once in conversation.

Here is simple test-case: Let $R$ be the ring $\mathbb{Z}[t,\sqrt{2}t-r]$, where $r$ is a real transcendental and $t$ is an indeterminate. Order $R$ by declaring $t$ positive infinite. It is not hard to show that $R$ extends to a model of true arithmetic. I don't know if $R$ has an algebraic extension to a model of open induction.

Real algebraic sets bounded away from integer points

2011-01-28T12:21:16Z

A subset $S$ of $\mathbb{R}^n$ is "bounded away from integer points" if for some positive $\epsilon$ every point in $S$ lies at a distance of at least $\epsilon$ from $\mathbb{Z}^n$. For example the line $x+y=1/2$ in $\mathbb{R}^2$ is bounded away from integer points, but the curve $x^2+y=1/2$ is not, because the points $(n+\frac{1}{4n},-n^2-\frac{1}{16n^2})$ for $n=1,2,\ldots$ lie on this curve.

Question: Can anyone give an algorithm to determine whether a system of polynomial equations with real algebraic coefficients cuts out a subset $S$ of $\mathbb{R}^n$ that is bounded away from integer points? Is there a simple description of all such subsets $S$?

Remark: I have a vague notion that if $S$ is bounded away from integer points then this must be ``trivially'' verifiable, perhaps because $S$ projects on a linear affine subset of $\mathbb{R}^n$ that is obviously bounded away from integer points, but this is little more than guesswork. I don't actually know that the problem is decidable, but I would be surprised if it were not.

UPDATE: (I'll use this section to collect my latest thoughts on the problem.)

The situation is fairly transparent in $\mathbb{R}^2$, and the real problem is how things generalize to higher dimensions. Let $S$ be as above. Let $\lfloor\cdot\rfloor$ be the floor function, which will be applied to points coordinatewise. Then I propose the following conjecture:

There exists some translate of $S$ bounded away from integer points if and only if the set of all points $\lfloor p\rfloor$ for $p\in S$ is contained in a finite union of linear-affine subspaces of $\mathbb{R}^n$ (which will be defined over the rationals).

Answer by SJR for Real-closed fields minus existentials for Presburger-like power and multiplication?

2011-01-27T04:58:15Z

The comment in the slides asserts that every ordered integral domain extends to a real closed field, or equivalently that the universal theory of real closed fields is a subset of the unversal theory of ordered integral domains. Is this useful in practice to decide whether a universal sentence is true in the integers? Sure, in the trivial sense that, e.g. the diophantine equation $x^2+y^2+1=0$ has no integer solutions because it has no solutions in any real closed field.

To go further than this, one must add (to the universal theory of ordered integral domains) axioms that express some special property of the ring of integers, the most obvious of which is the discreteness axiom, which asserts that there is nothing between 0 and 1. We might hope that the resulting theory (the theory of discretely ordered rings) would have a computable set of universal consequences, but this is not known. Indeed, Hilbert's Tenth Problem for discretely ordered rings is a long-standing problem for which we don't seem to have even a plausible line of attack. See for example "Which curves over Z have coordinates in a discretely ordered ring?" by van den Dries.

Answer by SJR for Implication of Polignac's conjecture on prime distribution in models of PA

2011-01-07T16:12:05Z

For simplicity, take $d=2$. Then the the existence of a model of PA with at least one non-standard pair of twin primes is equivalent to the assertion

For all (fixed, standard) primes $p$ the sentence $$\phi_p:\forall x>p,\,\,\, x \textrm{ is not prime or } x+2 \textrm{ is not prime }$$ is not provable in PA.

Is it reasonable to spend lots of time hunting for a proof of this before the twin prime conjecture is resolved? My guess is "no" and here is why.

All known constructions of non-standard models of PA depend in some way on an oracle who can determine which sentences are consistent with PA, or who can determine which sets are and are not members of some non-principal ultrafiter. I have no objections to such arguments, but it is well to be clear about the awesome powers of such an oracle: Relative to where we are, this is the point of view of eternity. It would be remarkable indeed if any statement of elementry number theory could be derived from such general constructions, and to my knowledge, none ever has.

There is an analogy here with a paragraph in Hardy and Wright's number theory text. Let $c$ be the constant $.020300500000007\ldots$. The point is that the definition of $c$ depends on foreknowledge of the sequence of primes. Using $c$ we can give a very simple formula for the $n$th prime, which is, as Hardy remarks, completely useless for proving things about primes.

In the same vein, there is a frontspiece to a book, I think by Mahler, that says:

     If you want to make sausage you have to put some pork in the grinder.

It is dangerous to say never, and in spite of Tennenbaum's theorem, there might come a day when some representation of models of PA is discovered that allows one to get information about these models from some source other than the Peano axioms... but as far as I know, that day has not arrived. The closest thing to such a representation theorem I have ever seen is an unpublished theorem of Tennenbaum, proving that every countable model of PA can be embedded in $\mathbb{R}^{\omega}$ modulo the cofinite filter: In other words, you can think of the elements of models of PA as germs at infinity of sequences of real numbers. I once asked Greg Cherlin about the usefulness of this representation. His response was "There is no free lunch."

Approximating polynomials in R[x] using integer-valued polynomials

2010-12-28T08:15:43Z

An integer-valued polynomial is a polynomial with real coefficients mapping integers to integers. It is well known that all such polynomials $h(x)$ are generated as an additive group by the binomial coefficients $\binom{x}{n}$. My question concerns the problem of approximating an arbitrary polynomial $f$ with real coefficients on a skillfully chosen interval $I$ of length 1 by means of a skillfully chosen non-zero integer-valued polynomial $h$. Specifically, for $f\in\mathbb{R}[x]$ let $$N(f)=\inf_{I,h}\,\,\,\, ||f-h||_{I},$$ where $||\cdot ||_I$ means sup norm, $h$ runs through all non-zero integer-valued polynomials, and $I$ runs through all intervals of length 1. I am looking for a way to compute $N(f)$, and I have a conjecture (a guess really) that makes this computation very simple.

$\textbf{Conjecture:}$ Let $D(x)$ be the distance from the real number $x$ to the nearest integer. Then $$N(f)=\inf_{x\in\mathbb{Z}} \,\,\, D(f(x)).$$

My question is: Can anyone provide a proof or counter-example or some helpful references? In particular, as a simple test-case, can anyone compute $N(\frac{1}{2}x)$? Maybe the problem is impossibly difficult or ridiculously easy for some reason I don't see, and someone can put me out of my misery.

$\textbf{Remarks:}$

It is clear that $N(f)\ge\inf_{x\in\mathbb{Z}}D(f(x))$, because the closure of every interval of length 1 contains an integer.
I suspect that the conjecture is false if one defines $N$ so that $h$ ranges over polynomials with INTEGER coefficients, but I don't have an example to prove this.
It is easy to check that $N(0)$=0, and in general $N(c)=D(c)$ for any constant $c$, using the fact that the polynomial $\binom{x}{n}$ tends to 0 uniformly on $[0,1]$ as $n$ tends to infinity.
I'm already stuck on the computation of $N(\frac{1}{2}x)$, which is 0 according to the conjecture. One would naturally consider intervals $I$ of the form $[2n-\frac{1}{2},2n+\frac{1}{2}]$, and look at polynomials of the form $h(x):=\sum_{k}c_{k}\binom{x}{k}$, such that all the $c_{k}$ are integers and $h(2n)=n$.

Answer by SJR for Decision Procedure for Inequalities between Homogeneous Polynomials

2010-11-29T16:09:31Z

I can prove that the following problem is undecidable: To determine, given two homogenous polynomials $p_1$ and $p_2$ , whether or not the inequality $p_1\le p_2$ holds for all integer arguments.

Indeed, suppose there was an algorithm $A$ to determine whether $p_1\le p_2$ always holds. Then we can use this algorithm to determine whether any polynomial $f$ has an integer zero.

To see this, suppose $f=f(x_1,\ldots,,x_n)$ has total degree $d$. Let $$g(x_1,\ldots,,x_n,z)=z^d f(x_1/z,\ldots,x_n/z),$$ so $g$ is homogeneous of degree $d$.

I claim that $f$ has no integer zero if and only if the inequality $$2z^d\le g(x_1,\ldots,,x_n,z)^2+z^{2d} $$ holds for all integer arguments. Note that the left and right hand sides are homogeneous polynomials, so if the claim is true then we can we can use algorithm $A$ to decide whether or not $f$ has an integer zero.

To verify the claim, suppose first that $f$ has no integer zero. If $z=1$ then the inequality reduces to $2\le g(x_1,\ldots,,x_n,1)^2+1$ , i.e., $1\le f(x_1,\ldots,,x_n)^2$ . If $z$ is different than 1, then already $2z^d\le z^{2d}$ , therefore $2z^d\le g(x_1,\ldots,,x_n,z)^2+z^{2d}$ . So if $f$ has no integer zero then the inequality holds for all integer arguments.

Conversely, if the inequality holds for all integer arguments, then put $z=1$ to obtain $1\le f(x_1,\ldots,,x_n)^2$ .

What about the case that the coefficients of the $p_i$ are assumed to be positive? It would be interesting if in this case the problem was decidable.

Distribution mod 1 of Factorial Multiples of Real Numbers.

2010-11-11T08:12:41Z

Let $c$ be an irrational real number. Let $\{\cdot\}$ be the fractional part operator. I would like to get some sense of how in-the-dark we are about the distribution of values of $\{cn!\}$ , for familiar values of $c$. This is related to a previous post which (essentially) asks the question "Does $n!/(2\pi)$ tend to a limit mod 1?"

Here is the question: Can anyone give a value of $c$ which is either algebraic, or a familiar transcendental, or defined in some reasonably simple way using the elementary functions of calculus, such that

$\{cn!\}<1/2$ infinitely often, or
$\{cn!\}$ tends to a limit, or
The values of $\{cn!\}$ are dense in the interval $[0,1]$ .

What do I know that we know about all this? First of all, it is a theorem of P. Diaconis (The Annals of Probability 1977, v5) that $\log(n!)$ is uniformly distibuted mod 1. This has the consequence that any sequence of leading (most significant) digits appears infinitely often. This is probably not going to be of any direct help, but it seems like it deserves to be mentioned.

Secondly, and importantly, it is known that for any lacunary sequence of positive integers $a_n$ (meaning that there is a fixed $\rho>1$ such that the inequality $a_{n+1}>\rho a_n$ holds for all large enough $n$) there are real numbers $c$ such that the sequence $\{ca_n\}$ is bounded away from 0 mod 1, and in fact the set of such real numbers has Hausdorff dimension 1. This is trivial to prove for $\rho > 2$ , and in fact in this case we can easily choose $c$ (nonconstuctively!) to get any of the behaviors described in Items 1,2 and 3.

For $\rho$ near 1 the above statement about lacunary sequences was an Erdos problem, first solved by B. de Mathan (Acta Math. Hungar. 1980 v36). There is an exposition by Katznelson here.

Since the sequence $n!$ is lacunary (with $\rho$ as large as one wants) we already know that the behaviors described in Items 1-3 occur in abundance. The question is whether we know any specific examples.

Answer by SJR for "Linear algebra" over Z/nZ - reference please!

2010-11-03T15:51:55Z

Your idea of using Smith normal form leads directly to a solution: But you need to verify that for every matrix $M$ with entries in $\mathbb{Z}/n\mathbb{Z}$ there are invertible matrices $A$ and $B$ with entries in $\mathbb{Z}/n\mathbb{Z}$ such that $AMB$ is in Smith normal form. It is essential that $A$ and $B$ be invertible as matrices over $\mathbb{Z}/n\mathbb{Z}$, otherwise the row and column spaces of $AMB$ won't necessarily be the same size as those of $M$.

A ring with the property that every matrix is equivalent to one in Smith normal form is called an elementary divisor ring. In the book "Matrices over Commutative Rings" by William Brown (Marcel Dekker 1993) it is shown (Theorem 15.8 and 15.9) that every principal ideal ring is an elementary divisor ring. It is simple to check that the rings $\mathbb{Z}/n\mathbb{Z}$ are principal ideal rings. So there's the reference you asked for. If you can't find the book by Brown the article by Kaplansky mentioned in the comments has the same material in a more general setting.

Is a real power series that maps rationals to rationals defined by a rational function?

2010-10-17T05:41:14Z

Suppose that the function $p(x)$ is defined on an open subset $U$ of $\mathbb{R}$ by a power series with real coefficients. Suppose, further, that $p$ maps rationals to rationals. Must $p$ be defined on $U$ by a rational function?

Comment by SJR

2013-05-16T10:22:39Z

Sorry, that link is broken. Use this: math.helsinki.fi/logic/people/juliette.kennedy/… Why can't I delete comments any more ??!!

Comment by SJR

2013-05-16T10:17:46Z

The module can't be free because the germ of the sequence n! is divisible. <\a href="duckduckgo.com/…; is a paper that studies this module (actually ring) in the context of models of arithmetic.

Comment by SJR

2013-05-10T10:22:02Z

@Laurent: Yes it really is surprising that we get the definability of N without extra constants, and the proof is extremely clever. Nevertheless, my intuition is that the full first-order theory is in general wildly unrelated to the existential theory.

Comment by SJR

2013-05-08T18:40:45Z

@David: You could ask the kind of question you are intersted in, using in place of R some countable subfield of the reals with a nice simple presentation, like the real algebraics. This leads to a complicated network of open and partially solved problems. See "Undecidability of Existential Theories of Rings and fields", by Pheidas and Zahidi, which I believe is available online.

Comment by SJR

2013-05-08T18:19:39Z

@David: Let's put it this way: If we allow coefficients in R(t) then we are asking about the effective computability of an uncountable set. This should seem a little bit uncomfortable!

Comment by SJR

2013-05-08T18:11:35Z

@David: This came up in the comments when the question was first posted. It was established that the coefficients must lie in some subring for which questions of decidability make sense. The OP concurred, and left it open what subring to choose, subject to this requirement. I chose the integers, or just as good, the rationals. In any case the question doesn't make good sense if we allow coefficients in R(t), unless we introduce some exotic definition of decidability, and there are many. But then we are in territory far from the OP's intent.

Comment by SJR

2013-05-08T17:41:44Z

@David: The polynomial equations in question are solvable in $\mathbb{R}(t)$ if and only if they are solvable in $\mathbbr{R}$. Why? On the one hand $\mathbb{R}$ is infinite: Give a solution in $\mathbb{R}(t)$ we can pick a real at which all the components are defined and substitute to get a solution in $\mathbb{R}$. Conversely, a solution in $\mathbb{R}$ is already a solution in $\mathbb{R}(t)$. So the rings $\mathbb{R}$ and $\mathbb{R}(t)$ have the same existential theories. But quantifier elimination for real closed fields gives an algorithm for deciding the existential theory of R.

Comment by SJR

2013-05-08T17:03:38Z

At least "archimedian" is necessary for Robinson's argument. Whether it is actually required I don't know

Comment by SJR

2013-05-08T16:59:30Z

Whoops! Archimedian is necessary. I've edited. And hello Joel! Greetings from Thailand. Yes, the subring here can be the rationals, or the integers.

Comment by SJR

2013-05-06T20:01:34Z

@Emil: Ok, thanks. I don't have access to the paper, but I suppose $p=0$ reduces to some form of Pell's equation. I hadn't noticed.

Comment by SJR

2013-05-06T17:57:37Z

@Emil: To make your proof work, I need some DOR in which $f$ has a zero. To make this happen I must satisfy in some DOR the three equations (1) $p(a, (1+\sum_iu_i^2)(a-1)+1, (1+\sum_iu_i^2+\sum_iv_i^2)(a-1))=0$, (2) $a=\sum_iw_i^2$, and (3) $q(w)=0$. I have no problem with (2) and (3), but given solutions to (2) and (3) in some DOR, how do I know that there are $u$'s and $v$'s that will satisfy (1)?

Comment by SJR

2013-05-06T15:45:01Z

@Emil: You "take a root of $f$ in a DOR $R$..." Why is it obvious that if $p(a,x,y):=x^2+2axy+y^2-1$ then the equation $p(a,(1+\sum_iu_i^2)(a-1)-1,(1+\sum_iu_i^2+\sum_iv_i^2)(a-1))=0$ has a solution in some DOR?

Comment by SJR

2013-05-06T10:27:17Z

The coefficients of the polynomials in $S$ need to have some cannonical, finitary presentation in order for the question to be well-posed. Perhaps you would be content with coefficients in the prime subring?

Comment by SJR

2013-05-06T09:28:50Z

@Emil: I just found your response. Thank you very much! I'll need some time to digest this...

Comment by SJR

2013-04-23T17:28:12Z

@Joel, Emil: My hope is that DOR is so weak that some construction will give a zero in a rank 1 DOR, merely because DOR$+\exists x,y\,f(x,y)=0$ is consistent. It is a longstanding open problem to effectively determine if an arbitrary polynomial has a zero in at least one DOR. It would be nice if we only had to look at rank 1 DOR's.