text:
You are currently browsing the category archive for the 'math.LO' category.
As readers who have followed my previous post will know, I have been spending the last few weeks extending my previous interactive text on propositional logic (entitied "QED") to also cover first-order logic. The text has now reached what seems to be a stable form, with a complete set of deductive rules for first-order logic with equality, and no major bugs as far as I can tell (apart from one weird visual bug I can't eradicate, in that some graphics elements can occasionally temporarily disappear when one clicks on an item). So it will likely not change much going forward.
I feel though that there could be more that could be done with this sort of framework (e.g., improved GUI, modification to other logics, developing the ability to write one's own texts and libraries, exploring mathematical theories such as Peano arithmetic, etc.). But writing this text (particularly the first-order logic sections) has brought me close to the limit of my programming ability, as the number of bugs introduced with each new feature implemented has begun to grow at an alarming rate. I would like to repackage the code so that it can be re-used by more adept programmers for further possible applications, though I have never done something like this before and would appreciate advice on how to do so. The code is already available under a Creative Commons licence, but I am not sure how readable and modifiable it will be to others currently. [Update: it is now on GitHub.]
[One thing I noticed is that I would probably have to make more of a decoupling between the GUI elements, the underlying logical elements, and the interactive text. For instance, at some point I made the decision (convenient at the time) to use some GUI elements to store some of the state variables of the text, e.g. the exercise buttons are currently storing the status of what exercises are unlocked or not. This is presumably not an example of good programming practice, though it would be relatively easy to fix. More seriously, due to my inability to come up with a good general-purpose matching algorithm (or even specification of such an algorithm) for the the laws of first-order logic, many of the laws have to be hard-coded into the matching routine, so one cannot currently remove them from the text. It may well be that the best thing to do in fact is to rework the entire codebase from scratch using more professional software design methods.]
[Update, Aug 23: links moved to GitHub version.]
About six years ago on this blog, I started thinking about trying to make a web-based game based around high-school algebra, and ended up using Scratch to write a short but playable puzzle game in which one solves linear equations for an unknown using a restricted set of moves. (At almost the same time, there were a number of more professionally made games released along similar lines, most notably Dragonbox.)
Since then, I have thought a couple times about whether there were other parts of mathematics which could be gamified in a similar fashion. Shortly after my first blog posts on this topic, I experimented with a similar gamification of Lewis Carroll's classic list of logic puzzles, but the results were quite clunky, and I was never satisfied with the results.
Over the last few weeks I returned to this topic though, thinking in particular about how to gamify the rules of inference of propositional logic, in a manner that at least vaguely resembles how mathematicians actually go about making logical arguments (e.g., splitting into cases, arguing by contradiction, using previous result as lemmas to help with subsequent ones, and so forth). The rules of inference are a list of a dozen or so deductive rules concerning propositional sentences (things like "( AND ) OR (NOT )", where are some formulas). A typical such rule is Modus Ponens: if the sentence is known to be true, and the implication " IMPLIES " is also known to be true, then one can deduce that is also true. Furthermore, in this deductive calculus it is possible to temporarily introduce some unproven statements as an assumption, only to discharge them later. In particular, we have the deduction theorem: if, after making an assumption , one is able to derive the statement , then one can conclude that the implication " IMPLIES " is true without any further assumption.
It took a while for me to come up with a workable game-like graphical interface for all of this, but I finally managed to set one up, now using Javascript instead of Scratch (which would be hopelessly inadequate for this task); indeed, part of the motivation of this project was to finally learn how to program in Javascript, which turned out to be not as formidable as I had feared (certainly having experience with other C-like languages like C++, Java, or lua, as well as some prior knowledge of HTML, was very helpful). The main code for this project is available here. Using this code, I have created an interactive textbook in the style of a computer game, which I have titled "QED". This text contains thirty-odd exercises arranged in twelve sections that function as game "levels", in which one has to use a given set of rules of inference, together with a given set of hypotheses, to reach a desired conclusion. The set of available rules increases as one advances through the text; in particular, each new section gives one or more rules, and additionally each exercise one solves automatically becomes a new deduction rule one can exploit in later levels, much as lemmas and propositions are used in actual mathematics to prove more difficult theorems. The text automatically tries to match available deduction rules to the sentences one clicks on or drags, to try to minimise the amount of manual input one needs to actually make a deduction.
Most of one's proof activity takes place in a "root environment" of statements that are known to be true (under the given hypothesis), but for more advanced exercises one has to also work in sub-environments in which additional assumptions are made. I found the graphical metaphor of nested boxes to be useful to depict this tree of sub-environments, and it seems to combine well with the drag-and-drop interface.
The text also logs one's moves in a more traditional proof format, which shows how the mechanics of the game correspond to a traditional mathematical argument. My hope is that this will give students a way to understand the underlying concept of forming a proof in a manner that is more difficult to achieve using traditional, non-interactive textbooks.
I have tried to organise the exercises in a game-like progression in which one first works with easy levels that train the player on a small number of moves, and then introduce more advanced moves one at a time. As such, the order in which the rules of inference are introduced is a little idiosyncratic. The most powerful rule (the law of the excluded middle, which is what separates classical logic from intuitionistic logic) is saved for the final section of the text.
Anyway, I am now satisfied enough with the state of the code and the interactive text that I am willing to make both available (and open source; I selected a CC-BY licence for both), and would be happy to receive feedback on any aspect of the either. In principle one could extend the game mechanics to other mathematical topics than the propositional calculus – the rules of inference for first-order logic being an obvious next candidate – but it seems to make sense to focus just on propositional logic for now.
In graph theory, the recently developed theory of graph limits has proven to be a useful tool for analysing large dense graphs, being a convenient reformulation of the Szemerédi regularity lemma. Roughly speaking, the theory asserts that given any sequence of finite graphs, one can extract a subsequence which converges (in a specific sense) to a continuous object known as a "graphon" – a symmetric measurable function . What "converges" means in this context is that subgraph densities converge to the associated integrals of the graphon . For instance, the edge density
converge to the integral
the triangle density
converges to the integral
the four-cycle density
converges to the integral
and so forth. One can use graph limits to prove many results in graph theory that were traditionally proven using the regularity lemma, such as the triangle removal lemma, and can also reduce many asymptotic graph theory problems to continuous problems involving multilinear integrals (although the latter problems are not necessarily easy to solve!). See this text of Lovasz for a detailed study of graph limits and their applications.
One can also express graph limits (and more generally hypergraph limits) in the language of nonstandard analysis (or of ultraproducts); see for instance this paper of Elek and Szegedy, Section 6 of this previous blog post, or this paper of Towsner. (In this post we assume some familiarity with nonstandard analysis, as reviewed for instance in the previous blog post.) Here, one starts as before with a sequence of finite graphs, and then takes an ultraproduct (with respect to some arbitrarily chosen non-principal ultrafilter ) to obtain a nonstandard graph , where is the ultraproduct of the , and similarly for the . The set can then be viewed as a symmetric subset of which is measurable with respect to the Loeb -algebra of the product (see this previous blog post for the construction of Loeb measure). A crucial point is that this -algebra is larger than the product of the Loeb -algebra of the individual vertex set . This leads to a decomposition
where the "graphon" is the orthogonal projection of onto , and the "regular error" is orthogonal to all product sets for . The graphon then captures the statistics of the nonstandard graph , in exact analogy with the more traditional graph limits: for instance, the edge density
(or equivalently, the limit of the along the ultrafilter ) is equal to the integral
where denotes Loeb measure on a nonstandard finite set ; the triangle density
(or equivalently, the limit along of the triangle densities of ) is equal to the integral
and so forth. Note that with this construction, the graphon is living on the Cartesian square of an abstract probability space , which is likely to be inseparable; but it is possible to cut down the Loeb -algebra on to minimal countable -algebra for which remains measurable (up to null sets), and then one can identify with , bringing this construction of a graphon in line with the traditional notion of a graphon. (See Remark 5 of this previous blog post for more discussion of this point.)
Additive combinatorics, which studies things like the additive structure of finite subsets of an abelian group , has many analogies and connections with asymptotic graph theory; in particular, there is the arithmetic regularity lemma of Green which is analogous to the graph regularity lemma of Szemerédi. (There is also a higher order arithmetic regularity lemma analogous to hypergraph regularity lemmas, but this is not the focus of the discussion here.) Given this, it is natural to suspect that there is a theory of "additive limits" for large additive sets of bounded doubling, analogous to the theory of graph limits for large dense graphs. The purpose of this post is to record a candidate for such an additive limit. This limit can be used as a substitute for the arithmetic regularity lemma in certain results in additive combinatorics, at least if one is willing to settle for qualitative results rather than quantitative ones; I give a few examples of this below the fold.
It seems that to allow for the most flexible and powerful manifestation of this theory, it is convenient to use the nonstandard formulation (among other things, it allows for full use of the transfer principle, whereas a more traditional limit formulation would only allow for a transfer of those quantities continuous with respect to the notion of convergence). Here, the analogue of a nonstandard graph is an ultra approximate group in a nonstandard group , defined as the ultraproduct of finite -approximate groups for some standard . (A -approximate group is a symmetric set containing the origin such that can be covered by or fewer translates of .) We then let be the external subgroup of generated by ; equivalently, is the union of over all standard . This space has a Loeb measure , defined by setting
whenever is an internal subset of for any standard , and extended to a countably additive measure; the arguments in Section 6 of this previous blog post can be easily modified to give a construction of this measure.
The Loeb measure is a translation invariant measure on , normalised so that has Loeb measure one. As such, one should think of as being analogous to a locally compact abelian group equipped with a Haar measure. It should be noted though that is not actually a locally compact group with Haar measure, for two reasons:
- There is not an obvious topology on that makes it simultaneously locally compact, Hausdorff, and -compact. (One can get one or two out of three without difficulty, though.)
- The addition operation is not measurable from the product Loeb algebra to . Instead, it is measurable from the coarser Loeb algebra to (compare with the analogous situation for nonstandard graphs).
Nevertheless, the analogy is a useful guide for the arguments that follow.
Let denote the space of bounded Loeb measurable functions (modulo almost everywhere equivalence) that are supported on for some standard ; this is a complex algebra with respect to pointwise multiplication. There is also a convolution operation , defined by setting
whenever , are bounded nonstandard functions (extended by zero to all of ), and then extending to arbitrary elements of by density. Equivalently, is the pushforward of the -measurable function under the map .
The basic structural theorem is then as follows.
Theorem 1 (Kronecker factor) Let be an ultra approximate group. Then there exists a (standard) locally compact abelian group of the form
for some standard and some compact abelian group , equipped with a Haar measure and a measurable homomorphism (using the Loeb -algebra on and the Baire -algebra on ), with the following properties:
- (i) has dense image, and is the pushforward of Loeb measure by .
- (ii) There exists sets with open and compact, such that
- (iii) Whenever with compact and open, there exists a nonstandard finite set such that
- (iv) If , then we have the convolution formula
where are the pushforwards of to , the convolution on the right-hand side is convolution using , and is the pullback map from to . In particular, if , then for all .
One can view the locally compact abelian group as a "model "or "Kronecker factor" for the ultra approximate group (in close analogy with the Kronecker factor from ergodic theory). In the case that is a genuine nonstandard finite group rather than an ultra approximate group, the non-compact components of the Kronecker group are trivial, and this theorem was implicitly established by Szegedy. The compact group is quite large, and in particular is likely to be inseparable; but as with the case of graphons, when one is only studying at most countably many functions , one can cut down the size of this group to be separable (or equivalently, second countable or metrisable) if desired, so one often works with a "reduced Kronecker factor" which is a quotient of the full Kronecker factor . Once one is in the separable case, the Baire sigma algebra is identical with the more familiar Borel sigma algebra.
Given any sequence of uniformly bounded functions for some fixed , we can view the function defined by
as an "additive limit" of the , in much the same way that graphons are limits of the indicator functions . The additive limits capture some of the statistics of the , for instance the normalised means
converge (along the ultrafilter ) to the mean
and for three sequences of functions, the normalised correlation
converges along to the correlation
the normalised Gowers norm
converges along to the Gowers norm
and so forth. We caution however that some correlations that involve evaluating more than one function at the same point will not necessarily be preserved in the additive limit; for instance the normalised norm
does not necessarily converge to the norm
but can converge instead to a larger quantity, due to the presence of the orthogonal projection in the definition (4) of .
An important special case of an additive limit occurs when the functions involved are indicator functions of some subsets of . The additive limit does not necessarily remain an indicator function, but instead takes values in (much as a graphon takes values in even though the original indicators take values in ). The convolution is then the ultralimit of the normalised convolutions ; in particular, the measure of the support of provides a lower bound on the limiting normalised cardinality of a sumset. In many situations this lower bound is an equality, but this is not necessarily the case, because the sumset could contain a large number of elements which have very few () representations as the sum of two elements of , and in the limit these portions of the sumset fall outside of the support of . (One can think of the support of as describing the "essential" sumset of , discarding those elements that have only very few representations.) Similarly for higher convolutions of . Thus one can use additive limits to partially control the growth of iterated sumsets of subsets of approximate groups , in the regime where stays bounded and goes to infinity.
Theorem 1 can be proven by Fourier-analytic means (combined with Freiman's theorem from additive combinatorics), and we will do so below the fold. For now, we give some illustrative examples of additive limits.
Example 2 (Bohr sets) We take to be the intervals , where is a sequence going to infinity; these are -approximate groups for all . Let be an irrational real number, let be an interval in , and for each natural number let be the Bohr set
In this case, the (reduced) Kronecker factor can be taken to be the infinite cylinder with the usual Lebesgue measure . The additive limits of and end up being and , where is the finite cylinder
and is the rectangle
Geometrically, one should think of and as being wrapped around the cylinder via the homomorphism , and then one sees that is converging in some normalised weak sense to , and similarly for and . In particular, the additive limit predicts the growth rate of the iterated sumsets to be quadratic in until becomes comparable to , at which point the growth transitions to linear growth, in the regime where is bounded and is large.
If were rational instead of irrational, then one would need to replace by the finite subgroup here.
Example 3 (Structured subsets of progressions) We take be the rank two progression
where is a sequence going to infinity; these are -approximate groups for all . Let be the subset
Then the (reduced) Kronecker factor can be taken to be with Lebesgue measure , and the additive limits of the and are then and , where is the square
and is the circle
Geometrically, the picture is similar to the Bohr set one, except now one uses a Freiman homomorphism for to embed the original sets into the plane . In particular, one now expects the growth rate of the iterated sumsets and to be quadratic in , in the regime where is bounded and is large.
Example 4 (Dissociated sets) Let be a fixed natural number, and take
where are randomly chosen elements of a large cyclic group , where is a sequence of primes going to infinity. These are -approximate groups. The (reduced) Kronecker factor can (almost surely) then be taken to be with counting measure, and the additive limit of is , where and is the standard basis of . In particular, the growth rates of should grow approximately like for bounded and large.
Example 5 (Random subsets of groups) Let be a sequence of finite additive groups whose order is going to infinity. Let be a random subset of of some fixed density . Then (almost surely) the Kronecker factor here can be reduced all the way to the trivial group , and the additive limit of the is the constant function . The convolutions then converge in the ultralimit (modulo almost everywhere equivalence) to the pullback of ; this reflects the fact that of the elements of can be represented as the sum of two elements of in ways. In particular, occupies a proportion of .
Example 6 (Trigonometric series) Take for a sequence of primes going to infinity, and for each let be an infinite sequence of frequencies chosen uniformly and independently from . Let denote the random trigonometric series
Then (almost surely) we can take the reduced Kronecker factor to be the infinite torus (with the Haar probability measure ), and the additive limit of the then becomes the function defined by the formula
In fact, the pullback is the ultralimit of the . As such, for any standard exponent , the normalised norm
can be seen to converge to the limit
The reader is invited to consider combinations of the above examples, e.g. random subsets of Bohr sets, to get a sense of the general case of Theorem 1.
It is likely that this theorem can be extended to the noncommutative setting, using the noncommutative Freiman theorem of Emmanuel Breuillard, Ben Green, and myself, but I have not attempted to do so here (see though this recent preprint of Anush Tserunyan for some related explorations); in a separate direction, there should be extensions that can control higher Gowers norms, in the spirit of the work of Szegedy.
Note: the arguments below will presume some familiarity with additive combinatorics and with nonstandard analysis, and will be a little sketchy in places.
Let be the algebraic closure of , that is to say the field of algebraic numbers. We fix an embedding of into , giving rise to a complex absolute value for algebraic numbers .
Let be of degree , so that is irrational. A classical theorem of Liouville gives the quantitative bound
for the irrationality of fails to be approximated by rational numbers , where depends on but not on . Indeed, if one lets be the Galois conjugates of , then the quantity is a non-zero natural number divided by a constant, and so we have the trivial lower bound
from which the bound (1) easily follows. A well known corollary of the bound (1) is that Liouville numbers are automatically transcendental.
The famous theorem of Thue, Siegel and Roth improves the bound (1) to
for any and rationals , where depends on but not on . Apart from the in the exponent and the implied constant, this bound is optimal, as can be seen from Dirichlet's theorem. This theorem is a good example of the ineffectivity phenomenon that affects a large portion of modern number theory: the implied constant in the notation is known to be finite, but there is no explicit bound for it in terms of the coefficients of the polynomial defining (in contrast to (1), for which an effective bound may be easily established). This is ultimately due to the reliance on the "dueling conspiracy" (or "repulsion phenomenon") strategy. We do not as yet have a good way to rule out one counterexample to (2), in which is far closer to than ; however we can rule out two such counterexamples, by playing them off of each other.
A powerful strengthening of the Thue-Siegel-Roth theorem is given by the subspace theorem, first proven by Schmidt and then generalised further by several authors. To motivate the theorem, first observe that the Thue-Siegel-Roth theorem may be rephrased as a bound of the form
for any algebraic numbers with and linearly independent (over the algebraic numbers), and any and , with the exception when or are rationally dependent (i.e. one is a rational multiple of the other), in which case one has to remove some lines (i.e. subspaces in ) of rational slope from the space of pairs to which the bound (3) does not apply (namely, those lines for which the left-hand side vanishes). Here can depend on but not on . More generally, we have
Theorem 1 (Schmidt subspace theorem) Let be a natural number. Let be linearly independent linear forms. Then for any , one has the bound
for all , outside of a finite number of proper subspaces of , where
and depends on and the , but is independent of .
Being a generalisation of the Thue-Siegel-Roth theorem, it is unsurprising that the known proofs of the subspace theorem are also ineffective with regards to the constant . (However, the number of exceptional subspaces may be bounded effectively; cf. the situation with the Skolem-Mahler-Lech theorem, discussed in this previous blog post.) Once again, the lower bound here is basically sharp except for the factor and the implied constant: given any with , a simple volume packing argument (the same one used to prove the Dirichlet approximation theorem) shows that for any sufficiently large , one can find integers , not all zero, such that
for all . Thus one can get comparable to in many different ways.
There are important generalisations of the subspace theorem to other number fields than the rationals (and to other valuations than the Archimedean valuation ); we will develop one such generalisation below.
The subspace theorem is one of many finiteness theorems in Diophantine geometry; in this case, it is the number of exceptional subspaces which is finite. It turns out that finiteness theorems are very compatible with the language of nonstandard analysis. (See this previous blog post for a review of the basics of nonstandard analysis, and in particular for the nonstandard interpretation of asymptotic notation such as and .) The reason for this is that a standard set is finite if and only if it contains no strictly nonstandard elements (that is to say, elements of ). This makes for a clean formulation of finiteness theorems in the nonstandard setting. For instance, the standard form of Bezout's theorem asserts that if are coprime polynomials over some field, then the curves and intersect in only finitely many points. The nonstandard version of this is then
Theorem 2 (Bezout's theorem, nonstandard form) Let be standard coprime polynomials. Then there are no strictly nonstandard solutions to .
Now we reformulate Theorem 1 in nonstandard language. We need a definition:
Definition 3 (General position) Let be nested fields. A point in is said to be in -general position if it is not contained in any hyperplane of definable over , or equivalently if one has
for any .
Theorem 4 (Schmidt subspace theorem, nonstandard version) Let be a standard natural number. Let be linearly independent standard linear forms. Let be a tuple of nonstandard integers which is in -general position (in particular, this forces to be strictly nonstandard). Then one has
where we extend from to (and also similarly extend from to ) in the usual fashion.
Observe that (as is usual when translating to nonstandard analysis) some of the epsilons and quantifiers that are present in the standard version become hidden in the nonstandard framework, being moved inside concepts such as "strictly nonstandard" or "general position". We remark that as is in -general position, it is also in -general position (as an easy Galois-theoretic argument shows), and the requirement that the are linearly independent is thus equivalent to being -linearly independent.
Exercise 1 Verify that Theorem 1 and Theorem 4 are equivalent. (Hint: there are only countably many proper subspaces of .)
We will not prove the subspace theorem here, but instead focus on a particular application of the subspace theorem, namely to counting integer points on curves. In this paper of Corvaja and Zannier, the subspace theorem was used to give a new proof of the following basic result of Siegel:
Theorem 5 (Siegel's theorem on integer points) Let be an irreducible polynomial of two variables, such that the affine plane curve either has genus at least one, or has at least three points on the line at infinity, or both. Then has only finitely many integer points .
This is a finiteness theorem, and as such may be easily converted to a nonstandard form:
Theorem 6 (Siegel's theorem, nonstandard form) Let be a standard irreducible polynomial of two variables, such that the affine plane curve either has genus at least one, or has at least three points on the line at infinity, or both. Then does not contain any strictly nonstandard integer points .
Note that Siegel's theorem can fail for genus zero curves that only meet the line at infinity at just one or two points; the key examples here are the graphs for a polynomial , and the Pell equation curves . Siegel's theorem can be compared with the more difficult theorem of Faltings, which establishes finiteness of rational points (not just integer points), but now needs the stricter requirement that the curve has genus at least two (to avoid the additional counterexample of elliptic curves of positive rank, which have infinitely many rational points).
The standard proofs of Siegel's theorem rely on a combination of the Thue-Siegel-Roth theorem and a number of results on abelian varieties (notably the Mordell-Weil theorem). The Corvaja-Zannier argument rebalances the difficulty of the argument by replacing the Thue-Siegel-Roth theorem by the more powerful subspace theorem (in fact, they need one of the stronger versions of this theorem alluded to earlier), while greatly reducing the reliance on results on abelian varieties. Indeed, for curves with three or more points at infinity, no theory from abelian varieties is needed at all, while for the remaining cases, one mainly needs the existence of the Abel-Jacobi embedding, together with a relatively elementary theorem of Chevalley-Weil which is used in the proof of the Mordell-Weil theorem, but is significantly easier to prove.
The Corvaja-Zannier argument (together with several further applications of the subspace theorem) is presented nicely in this Bourbaki expose of Bilu. To establish the theorem in full generality requires a certain amount of algebraic number theory machinery, such as the theory of valuations on number fields, or of relative discriminants between such number fields. However, the basic ideas can be presented without much of this machinery by focusing on simple special cases of Siegel's theorem. For instance, we can handle irreducible cubics that meet the line at infinity at exactly three points :
Theorem 7 (Siegel's theorem with three points at infinity) Siegel's theorem holds when the irreducible polynomial takes the form
for some quadratic polynomial and some distinct algebraic numbers .
Proof: We use the nonstandard formalism. Suppose for sake of contradiction that we can find a strictly nonstandard integer point on a curve of the indicated form. As this point is infinitesimally close to the line at infinity, must be infinitesimally close to one of ; without loss of generality we may assume that is infinitesimally close to .
We now use a version of the polynomial method, to find some polynomials of controlled degree that vanish to high order on the "arm" of the cubic curve that asymptotes to . More precisely, let be a large integer (actually will already suffice here), and consider the -vector space of polynomials of degree at most , and of degree at most in the variable; this space has dimension . Also, as one traverses the arm of , any polynomial in grows at a rate of at most , that is to say has a pole of order at most at the point at infinity . By performing Laurent expansions around this point (which is a non-singular point of , as the are assumed to be distinct), we may thus find a basis of , with the property that has a pole of order at most at for each .
From the control of the pole at , we have
for all . The exponents here become negative for , and on multiplying them all together we see that
This exponent is negative for large enough (or just take ). If we expand
for some algebraic numbers , then we thus have
for some standard . Note that the -dimensional vectors are linearly independent in , because the are linearly independent in . Applying the Schmidt subspace theorem in the contrapositive, we conclude that the -tuple is not in -general position. That is to say, one has a non-trivial constraint of the form
for some standard rational coefficients , not all zero. But, as is irreducible and cubic in , it has no common factor with the standard polynomial , so by Bezout's theorem (Theorem 2) the constraint (4) only has standard solutions, contradicting the strictly nonstandard nature of .
Exercise 2 Rewrite the above argument so that it makes no reference to nonstandard analysis. (In this case, the rewriting is quite straightforward; however, there will be a subsequent argument in which the standard version is significantly messier than the nonstandard counterpart, which is the reason why I am working with the nonstandard formalism in this blog post.)
A similar argument works for higher degree curves that meet the line at infinity in three or more points, though if the curve has singularities at infinity then it becomes convenient to rely on the Riemann-Roch theorem to control the dimension of the analogue of the space . Note that when there are only two or fewer points at infinity, though, one cannot get the negative exponent of needed to usefully apply the subspace theorem. To deal with this case we require some additional tricks. For simplicity we focus on the case of Mordell curves, although it will be convenient to work with more general number fields than the rationals:
Theorem 8 (Siegel's theorem for Mordell curves) Let be a non-zero integer. Then there are only finitely many integer solutions to . More generally, for any number field , and any nonzero , there are only finitely many algebraic integer solutions to , where is the ring of algebraic integers in .
Again, we will establish the nonstandard version. We need some additional notation:
Definition 9
We define an almost rational integer to be a nonstandard such that for some standard positive integer , and write for the -algebra of almost rational integers. If is a standard number field, we define an almost -integer to be a nonstandard such that for some standard positive integer , and write for the -algebra of almost -integers. We define an almost algebraic integer to be a nonstandard such that is a nonstandard algebraic integer for some standard positive integer , and write for the -algebra of almost algebraic integers.
Theorem 10 (Siegel for Mordell, nonstandard version) Let be a non-zero standard algebraic number. Then the curve does not contain any strictly nonstandard almost algebraic integer point.
Another way of phrasing this theorem is that if are strictly nonstandard almost algebraic integers, then is either strictly nonstandard or zero.
Exercise 3 Verify that Theorem 8 and Theorem 10 are equivalent.
Due to all the ineffectivity, our proof does not supply any bound on the solutions in terms of , even if one removes all references to nonstandard analysis. It is a conjecture of Hall (a special case of the notorious ABC conjecture) that one has the bound for all (or equivalently ), but even the weaker conjecture that are of polynomial size in is open. (The best known bounds are of exponential nature, and are proven using a version of Baker's method: see for instance this text of Sprindzuk.)
A direct repetition of the arguments used to prove Theorem 7 will not work here, because the Mordell curve only hits the line at infinity at one point, . To get around this we will exploit the fact that the Mordell curve is an elliptic curve and thus has a group law on it. We will then divide all the integer points on this curve by two; as elliptic curves have four 2-torsion points, this will end up placing us in a situation like Theorem 7, with four points at infinity. However, there is an obstruction: it is not obvious that dividing an integer point on the Mordell curve by two will produce another integer point. However, this is essentially true (after enlarging the ring of integers slightly) thanks to a general principle of Chevalley and Weil, which can be worked out explicitly in the case of division by two on Mordell curves by relatively elementary means (relying mostly on unique factorisation of ideals of algebraic integers). We give the details below the fold.
There are a number of ways to construct the real numbers , for instance
- as the metric completion of (thus, is defined as the set of Cauchy sequences of rationals, modulo Cauchy equivalence);
- as the space of Dedekind cuts on the rationals ;
- as the space of quasimorphisms on the integers, quotiented by bounded functions. (I believe this construction first appears in this paper of Street, who credits the idea to Schanuel, though the germ of this construction arguably goes all the way back to Eudoxus.)
There is also a fourth family of constructions that proceeds via nonstandard analysis, as a special case of what is known as the nonstandard hull construction. (Here I will assume some basic familiarity with nonstandard analysis and ultraproducts, as covered for instance in this previous blog post.) Given an unbounded nonstandard natural number , one can define two external additive subgroups of the nonstandard integers :
- The group of all nonstandard integers of magnitude less than or comparable to ; and
- The group of nonstandard integers of magnitude infinitesimally smaller than .
The group is a subgroup of , so we may form the quotient group . This space is isomorphic to the reals , and can in fact be used to construct the reals:
Proposition 1 For any coset of , there is a unique real number with the property that . The map is then an isomorphism between the additive groups and .
Proof: Uniqueness is clear. For existence, observe that the set is a Dedekind cut, and its supremum can be verified to have the required properties for .
In a similar vein, we can view the unit interval in the reals as the quotient
where is the nonstandard (i.e. internal) set ; of course, is not a group, so one should interpret as the image of under the quotient map (or , if one prefers). Or to put it another way, (1) asserts that is the image of with respect to the map .
In this post I would like to record a nice measure-theoretic version of the equivalence (1), which essentially appears already in standard texts on Loeb measure (see e.g. this text of Cutland). To describe the results, we must first quickly recall the construction of Loeb measure on . Given an internal subset of , we may define the elementary measure of by the formula
This is a finitely additive probability measure on the Boolean algebra of internal subsets of . We can then construct the Loeb outer measure of any subset in complete analogy with Lebesgue outer measure by the formula
where ranges over all sequences of internal subsets of that cover . We say that a subset of is Loeb measurable if, for any (standard) , one can find an internal subset of which differs from by a set of Loeb outer measure at most , and in that case we define the Loeb measure of to be . It is a routine matter to show (e.g. using the Carathéodory extension theorem) that the space of Loeb measurable sets is a -algebra, and that is a countably additive probability measure on this space that extends the elementary measure . Thus now has the structure of a probability space .
Now, the group acts (Loeb-almost everywhere) on the probability space by the addition map, thus for and (excluding a set of Loeb measure zero where exits ). This action is clearly seen to be measure-preserving. As such, we can form the invariant factor , defined by restricting attention to those Loeb measurable sets with the property that is equal -almost everywhere to for each .
The claim is then that this invariant factor is equivalent (up to almost everywhere equivalence) to the unit interval with Lebesgue measure (and the trivial action of ), by the same factor map used in (1). More precisely:
Theorem 2 Given a set , there exists a Lebesgue measurable set , unique up to -a.e. equivalence, such that is -a.e. equivalent to the set . Conversely, if is Lebesgue measurable, then is in , and .
More informally, we have the measure-theoretic version
of (1).
Proof: We first prove the converse. It is clear that is -invariant, so it suffices to show that is Loeb measurable with Loeb measure . This is easily verified when is an elementary set (a finite union of intervals). By countable subadditivity of outer measure, this implies that Loeb outer measure of is bounded by the Lebesgue outer measure of for any set ; since every Lebesgue measurable set differs from an elementary set by a set of arbitrarily small Lebesgue outer measure, the claim follows.
Now we establish the forward claim. Uniqueness is clear from the converse claim, so it suffices to show existence. Let . Let be an arbitrary standard real number, then we can find an internal set which differs from by a set of Loeb measure at most . As is -invariant, we conclude that for every , and differ by a set of Loeb measure (and hence elementary measure) at most . By the (contrapositive of the) underspill principle, there must exist a standard such that and differ by a set of elementary measure at most for all . If we then define the nonstandard function by the formula
then from the (nonstandard) triangle inequality we have
(say). On the other hand, has the Lipschitz continuity property
and so in particular we see that
for some Lipschitz continuous function . If we then let be the set where , one can check that differs from by a set of Loeb outer measure , and hence does so also. Sending to zero, we see (from the converse claim) that is a Cauchy sequence in and thus converges in for some Lebesgue measurable . The sets then converge in Loeb outer measure to , giving the claim.
Thanks to the Lebesgue differentiation theorem, the conditional expectation of a bounded Loeb-measurable function can be expressed (as a function on , defined -a.e.) as
By the abstract ergodic theorem from the previous post, one can also view this conditional expectation as the element in the closed convex hull of the shifts , of minimal norm. In particular, we obtain a form of the von Neumann ergodic theorem in this context: the averages for converge (as a net, rather than a sequence) in to .
If is (the standard part of) an internal function, that is to say the ultralimit of a sequence of finitary bounded functions, one can view the measurable function as a limit of the that is analogous to the "graphons" that emerge as limits of graphs (see e.g. the recent text of Lovasz on graph limits). Indeed, the measurable function is related to the discrete functions by the formula
for all , where is the nonprincipal ultrafilter used to define the nonstandard universe. In particular, from the Arzela-Ascoli diagonalisation argument there is a subsequence such that
thus is the asymptotic density function of the . For instance, if is the indicator function of a randomly chosen subset of , then the asymptotic density function would equal (almost everywhere, at least).
I'm continuing to look into understanding the ergodic theory of actions, as I believe this may allow one to apply ergodic theory methods to the "single-scale" or "non-asymptotic" setting (in which one averages only over scales comparable to a large parameter , rather than the traditional asymptotic approach of letting the scale go to infinity). I'm planning some further posts in this direction, though this is still a work in progress.
(This is an extended blog post version of my talk "Ultraproducts as a Bridge Between Discrete and Continuous Analysis" that I gave at the Simons institute for the theory of computing at the workshop "Neo-Classical methods in discrete analysis". Some of the material here is drawn from previous blog posts, notably "Ultraproducts as a bridge between hard analysis and soft analysis" and "Ultralimit analysis and quantitative algebraic geometry"'. The text here has substantially more details than the talk; one may wish to skip all of the proofs given here to obtain a closer approximation to the original talk.)
Discrete analysis, of course, is primarily interested in the study of discrete (or "finitary") mathematical objects: integers, rational numbers (which can be viewed as ratios of integers), finite sets, finite graphs, finite or discrete metric spaces, and so forth. However, many powerful tools in mathematics (e.g. ergodic theory, measure theory, topological group theory, algebraic geometry, spectral theory, etc.) work best when applied to continuous (or "infinitary") mathematical objects: real or complex numbers, manifolds, algebraic varieties, continuous topological or metric spaces, etc. In order to apply results and ideas from continuous mathematics to discrete settings, there are basically two approaches. One is to directly discretise the arguments used in continuous mathematics, which often requires one to keep careful track of all the bounds on various quantities of interest, particularly with regard to various error terms arising from discretisation which would otherwise have been negligible in the continuous setting. The other is to construct continuous objects as limits of sequences of discrete objects of interest, so that results from continuous mathematics may be applied (often as a "black box") to the continuous limit, which then can be used to deduce consequences for the original discrete objects which are quantitative (though often ineffectively so). The latter approach is the focus of this current talk.
The following table gives some examples of a discrete theory and its continuous counterpart, together with a limiting procedure that might be used to pass from the former to the latter:
|(Limit method)
|Ramsey theory
|Topological dynamics
|Density Ramsey theory
|Ergodic theory
|Furstenberg correspondence principle
|Graph/hypergraph regularity
|Measure theory
|Graph limits
|Polynomial regularity
|Linear algebra
|Structural decompositions
|Hilbert space geometry
|Fourier analysis
|Spectral theory
|Direct and inverse limits
|Quantitative algebraic geometry
|Algebraic geometry
|Discrete metric spaces
|Continuous metric spaces
|Gromov-Hausdorff limits
|Approximate group theory
|Topological group theory
|Model theory
As the above table illustrates, there are a variety of different ways to form a limiting continuous object. Roughly speaking, one can divide limits into three categories:
- Topological and metric limits. These notions of limits are commonly used by analysts. Here, one starts with a sequence (or perhaps a net) of objects in a common space , which one then endows with the structure of a topological space or a metric space, by defining a notion of distance between two points of the space, or a notion of open neighbourhoods or open sets in the space. Provided that the sequence or net is convergent, this produces a limit object , which remains in the same space, and is "close" to many of the original objects with respect to the given metric or topology.
- Categorical limits. These notions of limits are commonly used by algebraists. Here, one starts with a sequence (or more generally, a diagram) of objects in a category , which are connected to each other by various morphisms. If the ambient category is well-behaved, one can then form the direct limit or the inverse limit of these objects, which is another object in the same category , and is connected to the original objects by various morphisms.
- Logical limits. These notions of limits are commonly used by model theorists. Here, one starts with a sequence of objects or of spaces , each of which is (a component of) a model for given (first-order) mathematical language (e.g. if one is working in the language of groups, might be groups and might be elements of these groups). By using devices such as the ultraproduct construction, or the compactness theorem in logic, one can then create a new object or a new space , which is still a model of the same language (e.g. if the spaces were all groups, then the limiting space will also be a group), and is "close" to the original objects or spaces in the sense that any assertion (in the given language) that is true for the limiting object or space, will also be true for many of the original objects or spaces, and conversely. (For instance, if is an abelian group, then the will also be abelian groups for many .)
The purpose of this talk is to highlight the third type of limit, and specifically the ultraproduct construction, as being a "universal" limiting procedure that can be used to replace most of the limits previously mentioned. Unlike the topological or metric limits, one does not need the original objects to all lie in a common space in order to form an ultralimit ; they are permitted to lie in different spaces ; this is more natural in many discrete contexts, e.g. when considering graphs on vertices in the limit when goes to infinity. Also, no convergence properties on the are required in order for the ultralimit to exist. Similarly, ultraproduct limits differ from categorical limits in that no morphisms between the various spaces involved are required in order to construct the ultraproduct.
With so few requirements on the objects or spaces , the ultraproduct construction is necessarily a very "soft" one. Nevertheless, the construction has two very useful properties which make it particularly useful for the purpose of extracting good continuous limit objects out of a sequence of discrete objects. First of all, there is Łos's theorem, which roughly speaking asserts that any first-order sentence which is asymptotically obeyed by the , will be exactly obeyed by the limit object ; in particular, one can often take a discrete sequence of "partial counterexamples" to some assertion, and produce a continuous "complete counterexample" that same assertion via an ultraproduct construction; taking the contrapositives, one can often then establish a rigorous equivalence between a quantitative discrete statement and its qualitative continuous counterpart. Secondly, there is the countable saturation property that ultraproducts automatically enjoy, which is a property closely analogous to that of compactness in topological spaces, and can often be used to ensure that the continuous objects produced by ultraproduct methods are "complete" or "compact" in various senses, which is particularly useful in being able to upgrade qualitative (or "pointwise") bounds to quantitative (or "uniform") bounds, more or less "for free", thus reducing significantly the burden of "epsilon management" (although the price one pays for this is that one needs to pay attention to which mathematical objects of study are "standard" and which are "nonstandard"). To achieve this compactness or completeness, one sometimes has to restrict to the "bounded" portion of the ultraproduct, and it is often also convenient to quotient out the "infinitesimal" portion in order to complement these compactness properties with a matching "Hausdorff" property, thus creating familiar examples of continuous spaces, such as locally compact Hausdorff spaces.
Ultraproducts are not the only logical limit in the model theorist's toolbox, but they are one of the simplest to set up and use, and already suffice for many of the applications of logical limits outside of model theory. In this post, I will set out the basic theory of these ultraproducts, and illustrate how they can be used to pass between discrete and continuous theories in each of the examples listed in the above table.
Apart from the initial "one-time cost" of setting up the ultraproduct machinery, the main loss one incurs when using ultraproduct methods is that it becomes very difficult to extract explicit quantitative bounds from results that are proven by transferring qualitative continuous results to the discrete setting via ultraproducts. However, in many cases (particularly those involving regularity-type lemmas) the bounds are already of tower-exponential type or worse, and there is arguably not much to be lost by abandoning the explicit quantitative bounds altogether.
The classical foundations of probability theory (discussed for instance in this previous blog post) is founded on the notion of a probability space – a space (the sample space) equipped with a -algebra (the event space), together with a countably additive probability measure that assigns a real number in the interval to each event.
One can generalise the concept of a probability space to a finitely additive probability space, in which the event space is now only a Boolean algebra rather than a -algebra, and the measure is now only finitely additive instead of countably additive, thus when are disjoint events. By giving up countable additivity, one loses a fair amount of measure and integration theory, and in particular the notion of the expectation of a random variable becomes problematic (unless the random variable takes only finitely many values). Nevertheless, one can still perform a fair amount of probability theory in this weaker setting.
In this post I would like to describe a further weakening of probability theory, which I will call qualitative probability theory, in which one does not assign a precise numerical probability value to each event, but instead merely records whether this probability is zero, one, or something in between. Thus is now a function from to the set , where is a new symbol that replaces all the elements of the open interval . In this setting, one can no longer compute quantitative expressions, such as the mean or variance of a random variable; but one can still talk about whether an event holds almost surely, with positive probability, or with zero probability, and there are still usable notions of independence. (I will refer to classical probability theory as quantitative probability theory, to distinguish it from its qualitative counterpart.)
The main reason I want to introduce this weak notion of probability theory is that it becomes suited to talk about random variables living inside algebraic varieties, even if these varieties are defined over fields other than or . In algebraic geometry one often talks about a "generic" element of a variety defined over a field , which does not lie in any specified variety of lower dimension defined over . Once has positive dimension, such generic elements do not exist as classical, deterministic -points in , since of course any such point lies in the -dimensional subvariety of . There are of course several established ways to deal with this problem. One way (which one might call the "Weil" approach to generic points) is to extend the field to a sufficiently transcendental extension , in order to locate a sufficient number of generic points in . Another approach (which one might dub the "Zariski" approach to generic points) is to work scheme-theoretically, and interpret a generic point in as being associated to the zero ideal in the function ring of . However I want to discuss a third perspective, in which one interprets a generic point not as a deterministic object, but rather as a random variable taking values in , but which lies in any given lower-dimensional subvariety of with probability zero. This interpretation is intuitive, but difficult to implement in classical probability theory (except perhaps when considering varieties over or ) due to the lack of a natural probability measure to place on algebraic varieties; however it works just fine in qualitative probability theory. In particular, the algebraic geometry notion of being "generically true" can now be interpreted probabilistically as an assertion that something is "almost surely true".
It turns out that just as qualitative random variables may be used to interpret the concept of a generic point, they can also be used to interpret the concept of a type in model theory; the type of a random variable is the set of all predicates that are almost surely obeyed by . In contrast, model theorists often adopt a Weil-type approach to types, in which one works with deterministic representatives of a type, which often do not occur in the original structure of interest, but only in a sufficiently saturated extension of that structure (this is the analogue of working in a sufficiently transcendental extension of the base field). However, it seems that (in some cases at least) one can equivalently view types in terms of (qualitative) random variables on the original structure, avoiding the need to extend that structure. (Instead, one reserves the right to extend the sample space of one's probability theory whenever necessary, as part of the "probabilistic way of thinking" discussed in this previous blog post.) We illustrate this below the fold with two related theorems that I will interpret through the probabilistic lens: the "group chunk theorem" of Weil (and later developed by Hrushovski), and the "group configuration theorem" of Zilber (and again later developed by Hrushovski). For sake of concreteness we will only consider these theorems in the theory of algebraically closed fields, although the results are quite general and can be applied to many other theories studied in model theory.
Let be a field. A definable set over is a set of the form
where is a natural number, and is a predicate involving the ring operations of , the equality symbol , an arbitrary number of constants and free variables in , the quantifiers , boolean operators such as , and parentheses and colons, where the quantifiers are always understood to be over the field . Thus, for instance, the set of quadratic residues
is definable over , and any algebraic variety over is also a definable set over . Henceforth we will abbreviate "definable over " simply as "definable".
If is a finite field, then every subset of is definable, since finite sets are automatically definable. However, we can obtain a more interesting notion in this case by restricting the complexity of a definable set. We say that is a definable set of complexity at most if , and can be written in the form (1) for some predicate of length at most (where all operators, quantifiers, relations, variables, constants, and punctuation symbols are considered to have unit length). Thus, for instance, a hypersurface in dimensions of degree would be a definable set of complexity . We will then be interested in the regime where the complexity remains bounded, but the field size (or field characteristic) becomes large.
In a recent paper, I established (in the large characteristic case) the following regularity lemma for dense definable graphs, which significantly strengthens the Szemerédi regularity lemma in this context, by eliminating "bad" pairs, giving a polynomially strong regularity, and also giving definability of the cells:
Lemma 1 (Algebraic regularity lemma) Let be a finite field, let be definable non-empty sets of complexity at most , and let also be definable with complexity at most . Assume that the characteristic of is sufficiently large depending on . Then we may partition and with , with the following properties:
My original proof of this lemma was quite complicated, based on an explicit calculation of the "square"
of using the Lang-Weil bound and some facts about the étale fundamental group. It was the reliance on the latter which was the main reason why the result was restricted to the large characteristic setting. (I then applied this lemma to classify expanding polynomials over finite fields of large characteristic, but I will not discuss these applications here; see this previous blog post for more discussion.)
Recently, Anand Pillay and Sergei Starchenko (and independently, Udi Hrushovski) have observed that the theory of the étale fundamental group is not necessary in the argument, and the lemma can in fact be deduced from quite general model theoretic techniques, in particular using (a local version of) the concept of stability. One of the consequences of this new proof of the lemma is that the hypothesis of large characteristic can be omitted; the lemma is now known to be valid for arbitrary finite fields (although its content is trivial if the field is not sufficiently large depending on the complexity at most ).
Inspired by this, I decided to see if I could find yet another proof of the algebraic regularity lemma, again avoiding the theory of the étale fundamental group. It turns out that the spectral proof of the Szemerédi regularity lemma (discussed in this previous blog post) adapts very nicely to this setting. The key fact needed about definable sets over finite fields is that their cardinality takes on an essentially discrete set of values. More precisely, we have the following fundamental result of Chatzidakis, van den Dries, and Macintyre:
Proposition 2 Let be a finite field, and let .
- (Discretised cardinality) If is a non-empty definable set of complexity at most , then one has
where is a natural number, and is a positive rational number with numerator and denominator . In particular, we have .
- (Definable cardinality) Assume is sufficiently large depending on . If , and are definable sets of complexity at most , so that can be viewed as a definable subset of that is definably parameterised by , then for each natural number and each positive rational with numerator and denominator , the set
is definable with complexity , where the implied constants in the asymptotic notation used to define (4) are the same as those that appearing in (3). (Informally: the "dimension" and "measure" of depends definably on .)
We will take this proposition as a black box; a proof can be obtained by combining the description of definable sets over pseudofinite fields (discussed in this previous post) with the Lang-Weil bound (discussed in this previous post). (The former fact is phrased using nonstandard analysis, but one can use standard compactness-and-contradiction arguments to convert such statements to statements in standard analysis, as discussed in this post.)
The above proposition places severe restrictions on the cardinality of definable sets; for instance, it shows that one cannot have a definable set of complexity at most and cardinality , if is sufficiently large depending on . If are definable sets of complexity at most , it shows that for some rational with numerator and denominator ; furthermore, if , we may improve this bound to . In particular, we obtain the following "self-improving" properties:
- If are definable of complexity at most and for some , then (if is sufficiently small depending on and is sufficiently large depending on ) this forces .
- If are definable of complexity at most and for some and positive rational , then (if is sufficiently small depending on and is sufficiently large depending on ) this forces .
It turns out that these self-improving properties can be applied to the coefficients of various matrices (basically powers of the adjacency matrix associated to ) that arise in the spectral proof of the regularity lemma to significantly improve the bounds in that lemma; we describe how this is done below the fold. We also make some connections to the stability-based proofs of Pillay-Starchenko and Hrushovski.
The rectification principle in arithmetic combinatorics asserts, roughly speaking, that very small subsets (or, alternatively, small structured subsets) of an additive group or a field of large characteristic can be modeled (for the purposes of arithmetic combinatorics) by subsets of a group or field of zero characteristic, such as the integers or the complex numbers . The additive form of this principle is known as the Freiman rectification principle; it has several formulations, going back of course to the original work of Freiman. Here is one formulation as given by Bilu, Lev, and Ruzsa:
Proposition 1 (Additive rectification) Let be a subset of the additive group for some prime , and let be an integer. Suppose that . Then there exists a map into a subset of the integers which is a Freiman isomorphism of order in the sense that for any , one has
if and only if
Furthermore is a right-inverse of the obvious projection homomorphism from to .
The original version of the rectification principle allowed the sets involved to be substantially larger in size (cardinality up to a small constant multiple of ), but with the additional hypothesis of bounded doubling involved; see the above-mentioned papers, as well as this later paper of Green and Ruzsa, for further discussion.
The proof of Proposition 1 is quite short (see Theorem 3.1 of Bilu-Lev-Ruzsa); the main idea is to use Minkowski's theorem to find a non-trivial dilate of that is contained in a small neighbourhood of the origin in , at which point the rectification map can be constructed by hand.
Very recently, Codrut Grosu obtained an arithmetic analogue of the above theorem, in which the rectification map preserves both additive and multiplicative structure:
Theorem 2 (Arithmetic rectification) Let be a subset of the finite field for some prime , and let be an integer. Suppose that . Then there exists a map into a subset of the complex numbers which is a Freiman field isomorphism of order in the sense that for any and any polynomial of degree at most and integer coefficients of magnitude summing to at most , one has
if and only if
Note that it is necessary to use an algebraically closed field such as for this theorem, in contrast to the integers used in Proposition 1, as can contain objects such as square roots of which can only map to in the complex numbers (once is at least ).
Using Theorem 2, one can transfer results in arithmetic combinatorics (e.g. sum-product or Szemerédi-Trotter type theorems) regarding finite subsets of to analogous results regarding sufficiently small subsets of ; see the paper of Grosu for several examples of this. This should be compared with the paper of Vu, Wood, and Wood, which introduces a converse principle that embeds finite subsets of (or more generally, a characteristic zero integral domain) in a Freiman field-isomorphic fashion into finite subsets of for arbitrarily large primes , allowing one to transfer arithmetic combinatorical facts from the latter setting to the former.
Grosu's argument uses some quantitative elimination theory, and in particular a quantitative variant of a lemma of Chang that was discussed previously on this blog. In that previous blog post, it was observed that (an ineffective version of) Chang's theorem could be obtained using only qualitative algebraic geometry (as opposed to quantitative algebraic geometry tools such as elimination theory results with explicit bounds) by means of nonstandard analysis (or, in what amounts to essentially the same thing in this context, the use of ultraproducts). One can then ask whether one can similarly establish an ineffective version of Grosu's result by nonstandard means. The purpose of this post is to record that this can indeed be done without much difficulty, though the result obtained, being ineffective, is somewhat weaker than that in Theorem 2. More precisely, we obtain
Theorem 3 (Ineffective arithmetic rectification) Let . Then if is a field of characteristic at least for some depending on , and is a subset of of cardinality , then there exists a map into a subset of the complex numbers which is a Freiman field isomorphism of order .
Our arguments will not provide any effective bound on the quantity (though one could in principle eventually extract such a bound by deconstructing the proof of Proposition 4 below), making this result weaker than Theorem 2 (save for the minor generalisation that it can handle fields of prime power order as well as fields of prime order as long as the characteristic remains large).
Following the principle that ultraproducts can be used as a bridge to connect quantitative and qualitative results (as discussed in these previous blog posts), we will deduce Theorem 3 from the following (well-known) qualitative version:
Proposition 4 (Baby Lefschetz principle) Let be a field of characteristic zero that is finitely generated over the rationals. Then there is an isomorphism from to a subfield of .
This principle (first laid out in an appendix of Lefschetz's book), among other things, often allows one to use the methods of complex analysis (e.g. Riemann surface theory) to study many other fields of characteristic zero. There are many variants and extensions of this principle; see for instance this MathOverflow post for some discussion of these. I used this baby version of the Lefschetz principle recently in a paper on expanding polynomial maps.
Proof: We give two proofs of this fact, one using transcendence bases and the other using Hilbert's nullstellensatz.
We begin with the former proof. As is finitely generated over , it has finite transcendence degree, thus one can find algebraically independent elements of over such that is a finite extension of , and in particular by the primitive element theorem is generated by and an element which is algebraic over . (Here we use the fact that characteristic zero fields are separable.) If we then define by first mapping to generic (and thus algebraically independent) complex numbers , and then setting to be a complex root of of the minimal polynomial for over after replacing each with the complex number , we obtain a field isomorphism with the required properties.
Now we give the latter proof. Let be elements of that generate that field over , but which are not necessarily algebraically independent. Our task is then equivalent to that of finding complex numbers with the property that, for any polynomial with rational coefficients, one has
if and only if
Let be the collection of all polynomials with rational coefficients with , and be the collection of all polynomials with rational coefficients with . The set
is the intersection of countably many algebraic sets and is thus also an algebraic set (by the Hilbert basis theorem or the Noetherian property of algebraic sets). If the desired claim failed, then could be covered by the algebraic sets for . By decomposing into irreducible varieties and observing (e.g. from the Baire category theorem) that a variety of a given dimension over cannot be covered by countably many varieties of smaller dimension, we conclude that must in fact be covered by a finite number of such sets, thus
for some . By the nullstellensatz, we thus have an identity of the form
for some natural numbers , polynomials , and polynomials with coefficients in . In particular, this identity also holds in the algebraic closure of . Evaluating this identity at we see that the right-hand side is zero but the left-hand side is non-zero, a contradiction, and the claim follows.
From Proposition 4 one can now deduce Theorem 3 by a routine ultraproduct argument (the same one used in these previous blog posts). Suppose for contradiction that Theorem 3 fails. Then there exists natural numbers , a sequence of finite fields of characteristic at least , and subsets of of cardinality such that for each , there does not exist a Freiman field isomorphism of order from to the complex numbers. Now we select a non-principal ultrafilter , and construct the ultraproduct of the finite fields . This is again a field (and is a basic example of what is known as a pseudo-finite field); because the characteristic of goes to infinity as , it is easy to see (using Los's theorem) that has characteristic zero and can thus be viewed as an extension of the rationals .
Now let be the ultralimit of the , so that is the ultraproduct of the , then is a subset of of cardinality . In particular, if is the field generated by and , then is a finitely generated extension of the rationals and thus, by Proposition 4 there is an isomorphism from to a subfield of the complex numbers. In particular, are complex numbers, and for any polynomial with integer coefficients, one has
if and only if
By Los's theorem, we then conclude that for all sufficiently close to , one has for all polynomials of degree at most and whose coefficients are integers whose magnitude sums up to , one has
if and only if
But this gives a Freiman field isomorphism of order between and , contradicting the construction of , and Theorem 3 follows.


text:
Celebrating the life of Bruno "Gintaras" Juozas Barkauskas
Be the first to share your favorite memory, photo or story of Bruno "Gintaras". This memorial page is dedicated for family, friends and future generations to celebrate the life of their loved one.
We ask on behalf of the family that you keep your comments uplifting and appropriate to help all who come here to find comfort and healing.
Bruno/Gintaras Juozas Barkauskas born 5/17/1944 died 2/7/2019 age 74. Beloved husband of Otilija (Uzgiris) Barkauskas for 48 years, father to Ramune, Kestutis, Rima and Darius, father-in-law to Kathy (Walslager) and Deborah (Sim), and cherished grandfather of Evan, Karolina, Darius and Vaiva. He was the son of immigrants escaping persecution in Lithuania. He was a talented electrical engineer and manager with degrees from Illinois Institute of Technology (BSE), Northwestern (MSE) and University of Chicago (MBA). He worked for Bell Labs/ATT/Lucent Technologies for over 30 years and spent many years living in Japan and traveling the world. He loved skiing, traveling and above all sailing on his sailboat Nemesis
To plant a tree in memory of Bruno "Gintaras" Juozas Barkauskas, please visit our Tribute Store.
Previous Events
12401 South Archer Avenue
Lemont, IL 60439
12401 South Archer Avenue
Lemont, IL 60439
14911 127th Street
Lemont, IL 60439
Cemetery Details
4401 West 111th Street
Chicago, IL 60655

subset: commoncrawl


text:
How to choose to do the right thing when doing so will come at a cost.
Being moral isn't easy. If it were easy, everyone would do it. Even people who want to be moral have a problem being moral all the time. It just takes so much work to think through your actions properly and then, sometimes, being moral comes at a cost.
Sometimes it is just easier to be immoral or ammoral through omission than it is to stand up and do the right thing. This is one of the reasons why bystanders who witness bullying rarely do anything about it.
I've been asked to address this topic and I think the best way is to start by talking about Maslow's hierarchy of needs. (see: https://en.wikipedia.org/wiki/Maslow's_hierarchy_of_needs - if you are unfamiliar with this concept). Maslow was a Humanist and like all Humanists he was concerned with what motivates us humans to do what we do. Like, how do we choose the right thing when doing so comes at a cost?
The reason the concept of the hierarchy of needs is helpful is because it helps us understand that we have competing needs and how we choose to act is going to depend on what need we place highest in our hierarchy. Not being hurt is certainly something that everyone needs. It's easy to see why this need would trump our need and desire to be moral.
The way I solve this common dilemma for myself is to do four things.
1) Prioritize being moral. This is a hierarchy and if you don't prioritize being moral it will be trumped by your other needs.
2) Think Critically - Do a cost benefit analysis of acting vs. not acting. What will I likely accomplish by acting? Is it worth it? It is very easy to give in to the need to not be hurt, but even if you prioritize being moral, you still need to engage in some critical thinking to decide whether or not it is worth it to act. Is this easy? No. It's not. There is no guarantee that you will get it right. Moral reasoning is hard, but that's part of what it is to be moral. If you do this step and decide not to act, you will feel better about it than if give in before this step.
3) Remind yourself of your responsibilities. If you don't do this moral thing, who will? Humanism is about personal responsibility. Even if your cost benefit shows that nothing would be gained by your action, you may still want to do the right thing because it's the right thing to do. Part of your cost benefit must be whether you can live with yourself if you don't act. Additionally, you need to remember that by your actions, even if futile, you can inspire others to be more moral as well. And that may be worth it.
4) Can you be clever? Often, if you spend some time thinking about how best to accomplish your objectives, you can do the right thing and reduce or eliminate the harm that is directed at you for doing the right thing. I teach this actually in my anti-bullying programs. This is a bit Epicurean, you may want to sustain some harm for a longer term gain, in which case, it is totally worth it to do the right thing.
How do you convince yourself to do the right thing despite the pressure not to?


text:
You are currently browsing the tag archive for the 'sunday morning' tag.
The First Day
A prayer for Sunday morning
Today we celebrate Your magnificent splendour
For by Your hand You placed time in motion
From the first day of creation until this day
Your creative wonders have filled the universe
Today we celebrate Your mighty power
For by Your hand you raised Christ from the grave
From resurrection Sunday until this day
Your love has given life to all mankind
Father we thank you for today
We give this special day over to You
May we rest in Your presence
Bathe in Your goodness
And celebrate Your eternal life
This day and always
(A modern prayer for Sundays from http://www.lords-prayer-words.com)
Today, I took a vacation day and drove two and half hours from Omaha NE to Dannebrog NE (Where I was a pastor from 1985 to 1993) to fish with a dear friend, Dan. He was saved one Sunday when I gave an invitation during a Sunday morning sermon to repent and turn to Jesus for salvation. Dan has followed Jesus ever since!
The fishing was awesome! I am sunburn!
The fellowship was better!
Dan told me that recently he was praying and he ended up praying an hour on his knees!
That is how revival comes!
May we all spend much, much time on our knees in prayer!


text:
As an Army paratrooper, a prosecutor, judge and community activist, Judge Charles Price has long been a catalyst for change. It's a career that has prepared him well to lead an organization known for its mission to create jobs, opportunities and a better quality of life in Montgomery and the River Region. "Being Chairman of the Chamber is an honor, and I'm following in a long list of leaders who care deeply about Montgomery and have worked hard to make our city and region grow and prosper," said Price.
Price has worked in our state's justice system for more than five decades, as an Alabama assistant attorney general, Montgomery County Deputy District Attorney and then as a city judge and finally, as judge for the Fifteenth Judicial Circuit of Montgomery County.
When asked about his legacy and what he hopes he's leaving behind, he doesn't list his landmark cases (and there have been several). Instead, he stresses that he views his time as a prosecutor and on the bench as a service to the people of Montgomery County, and that one of his main goals was to break down barriers. "I always wanted to make sure that people who didn't feel comfortable talking to those they saw as 'authority' or the law, people who felt on the margins, that they felt like they could talk to me. I had a reputation as being approachable and open, as being the guy who would listen and if needed, help you find answers," he said.
He also had a reputation for running his courtroom with a firm yet gentle hand. He retired from the bench in 2015, but he hasn't really slowed down. Today, in addition to working as a private practice attorney and serving as the Chamber's Chairman of the Board, he's also serving as Senior Advisor to Mayor Strange. In his roles for both the city and Chamber, he's operating from his "tough but fair" perspective, believing it's just as applicable to economic development, job creation and the day-to-day duties of getting business done as it was in the courtroom.
He's also working to improve communication and understanding between different groups and interests, just as he tried to do in his previous career. "I am obviously not a businessman, but I do know what a good business climate can do for a place; it means jobs and that means stronger families, which means better schools. It adds up to a good future for all," he said. "And the more people invested in and involved in the area's business initiatives, the better things will be for everyone here. Everyone matters, and everyone has something to offer."
It's why he touts a culture of inclusiveness and equality that's rooted in things he witnessed while growing up in a working-class community right outside the city limits. He watched his parents and others, most with little education, work hard for their families, which instilled in him a strong work ethic and a burning ambition to do something big. "We all worked hard; there was no time to be idle," he said. "All the kids understood that we were supposed to do our best and to do something even better than our parents had been able to do."
He realized young that he was good at debate, which got people saying he'd probably be a lawyer or a minister. "My mom was hoping for minister," he said. "And I didn't really know what a lawyer was or what they did; I didn't know any." But then, when he was in ninth grade, Price learned what good lawyers do and how they do it, watching the drama of the modern civil rights movement unfold right in front of his eyes. "I knew then I wanted to do that, to be a lawyer and to make a difference in people's lives," he said.
He found more inspiration even closer to home. "There were some night clubs in our community, and I remember a couple of times when there was violence there, it seemed like the perpetrator got off too easily," he said. "I didn't understand how someone could commit a crime on a Friday night and by Saturday morning, be out of jail, walking around in our community again. The victim had no control in that situation; it was as if they and their suffering had no value." That cemented his commitment to pursuing law school and sparked the idea that as a lawyer, he would help the victims of crime.
After high school, he couldn't afford college, so he enlisted in the Army, and like his brothers before him, became a Special Forces paratrooper. He'd married his high school sweetheart, and she was studying at Tuskegee University. By the time his military service was done, she had gotten a teaching job in Virginia, so he joined her there and enrolled in Virginia Union College. After graduation, he went to law school at George Washington University in Washington D.C.
In 1973, with his law degree in hand and a desire to be a prosecutor in his heart, he happily moved back home to Montgomery to accept the position of Assistant Attorney General offered to him by Attorney General Bill Baxley. In 1974, Baxley appointed him as district attorney in Escambia County. He came back home again to serve as Montgomery County's deputy district attorney in 1975, where he prosecuted several major felony cases as well as some political corruption cases. "I enjoyed prosecutor work; I enjoyed helping victims and helping them get answers, no matter who they were," he said.
In 1982, Montgomery mayor Emory Folmar appointed Price as a municipal judge, making him the city's first African American in that position. "I was the first to wear a robe too," he said. "Others in that job took it a little casually. I like to think I professionalized that court." In 1983, Governor George Wallace appointed Price to be a Montgomery County Circuit Judge, a title he held for three more decades, as he was elected back onto the bench time and time again.
The sense of justice that he developed over his more than 40 years in courtrooms is part of the motivation behind his work for the city today. "I've always admired Mayor Strange's brand of leadership, and when I retired, I told him I wanted to help with the city's progress. I asked what I could do," Price said. "He asked me to serve as his advisor, and I'm proud to do it."
Price began by spearheading the city's Small and Minority Business Initiative. "I wanted to make sure those businesses got a chance to be a part of the economic progress going on in the city," he said. "The initiative, now a city resolution, says that for all of the city's outside contracts for services, we have a goal of 30 percent of those contracts going to small or minority businesses. So far, it's working extremely well."
One major aspect is making the information necessary to apply for city contracts readily and easily available. "We realized we needed to adequately explain the proper procedures and protocols to our small businesses," he said. But Price sees the initiative going beyond equal opportunity; he sees it building relationships as well. "We're now getting all these different companies and groups talking to each other, interacting, where maybe they weren't before, and not just on the worksite. We're bringing folks together — working together to drive the city forward — to the benefit of all."
Price also puts his debate and mediation skills to good use, handling administrative hearings for city employees. "What I'm often doing is putting out res, handling complaints," he said. "I look for answers and try to stop a molehill from becoming a mountain."
As the mayor's advisor and now as leader of the Chamber's board, Price has big plans and a bold vision for his city, and he thinks we're headed in the right direction. "Our current business climate is already disproving the stereotype this city has been under," he said, "and I want to get the black community even more involved in the Chamber. I want them to know that they shouldn't sit outside. Bring your questions inside. Get a seat at the table and discuss your ideas."
In his mind, it all boils down to everyone in the city and region working together toward a common goal: an improved quality of life. "As Chairman, I want to open this city up so that we all enjoy the fruits of our labors together. I believe in community the way Dr. King talked about it. I do believe the tent is large enough for all."
A CAREER BUILT on a Calling
2018 Chamber Chairman Judge Charles Price had a long and storied career as both a prosecutor and a judge, one defined by his willingness to often tackle difficult cases, make hard decisions and do it all with kindness. Here are a few highlights:
- He was Montgomery's first black city judge.
- He prosecuted "Peter Rabbit," an African-American gang member who killed an off-duty police officer in Montgomery.
- In 1997, he was honored with the John F. Kennedy Profile in Courage Award for "his devotion to the principles of the American Constitution" that compelled him to rule against Judge Roy Moore's display of the Ten Commandments in his courtroom. He is only the second Alabama citizen to earn the honor.
- He presided over the Torrey McNabb case and handed down a capital punishment sentence for McNabb, who killed a police officer in 1997. "Sometimes, it is appropriate, and it was in this case," Price said.
- In 2009, the Montgomery County Courthouse was renamed Montgomery County Courthouse, Phelps-Price Justice Center in memory of Judge Phelps and in honor of Judge Price.
- He was appointed to the Alabama Ethics Commission in 2016; his term ends in 2020.
The CHAIRMAN'S FOCUS
While Judge Price has a few projects particularly close to his heart, he stressed that part of what makes the Chamber so effective is having many partners rallied around one vision and following a plan. And that plan is the Imagine a Greater Montgomery strategy. "Having consistent goals that everyone is bought into is important," said Price. Each year, the Chamber takes stock of performance against the Imagine plan, and then makes adjustments as needed to capitalize on new opportunities. "Every year, a new implementation plan is developed that keeps our leadership focused on what's important and defines what success looks like," said Price.
Quality Public Schools: "The state intervention has opened up new opportunities to change out school system in Montgomery. As a community, we should expect no less than having every school be a quality choice for every child."
Increased Air Service & Passenger Traffic at MGM Regional Airport: "We have a new flight direct to Reagan National in DC starting in June. That is huge for Montgomery. We've got to make sure it's successful and keep growing our airport. We've got to capture passengers back from Birmingham and Atlanta, and we've got to understand that we must use our airport or be in jeopardy of losing it."
Small & Minority Business Development: "The Chamber has counseled, mentored or trained more than 14,000 entrepreneurs since 2010. That's impressive. But we can do more. We've got to reach out in new ways to meet our small and minority businesses where they are and work harder to connect them to the resources they need to prosper."
TechMGM & the innovation District: "We have major projects in play and partners working to leverage Montgomery's unique technology, military, Department of Defense, government and business assets. I expect some very exciting developments in innovation and technology this year that will fuel Montgomery's economy and transform the image of our city and region."


text:
EMail & SMS Marketing
Graphic Design is the process of creating modifications in something that can be seen. This is more a functional element when it comes to graphic designing. The requirement of skills is necessary for graphics designing.
It is a phenomenon of visualization communication by images, illustration etc. In this, the symbols, visuals, and images are combined to get a formidable and an organized output that turns out to be productive. Logos and brand signs are designed with the help of Graphic Designing. Web designing is a major function under graphic designers.
Both Creativity Service and Graphic Design are complementary to each other but more importantly, creativity is only a classification of Graphic designing.
Aligned tools for Graphic Designing
Here texture is basically the look or the visual feel being generated by the designer which works as the first impression for any website to offer the product.
Typography is all about setting up a mood through font display and size of the text by making it appealing.
Graphic Designing tends to follow the following principles:-
This is the ideal composition of the steps to be undertaken in order to facilitate efficient Graphic Designing.


text:
Our website uses cookies to improve your experience. Click here to see our Cookie Policy.
full list»
Our T.A.C packages offer maximum coverage with
on-the-page advertising,
stand-alone e-mail broadcasts, monthly bulletins and web site promotions.
healthcare buildings forum
visit hbf website»
mental health & dementiafacilities forum
visit mhdf website»
Healthcare furniture manufacturers, Pineapple Contracts are pleased to announce the arrival their of Cumulus Plus table range for challenging environments.
Building on the popularity of the original Cumulus range, the latest products have a wider pedestal base which accommodates additional weighting. This weight, combined with a solid steel base plate creates a very strong and stable option which is suitable for a variety of challenging environments including mental health and custodial environments. The table tops are made from a durable high pressure laminate top with PVC impact edging, and are available in a white or anthracite finish.
The Cumulus Plus range comprises a coffee table, square dining tables (3 sizes) and twin-pedestal rectangular dining tables (2 sizes).
Click here to find out more
To advertise in this space, click here to email Leslie de Hoog
© 2019 Stable Publishing Limited. All rights reserved. Terms of use Privacy policy Cookie policy
Website designed and developed by Netfactors Internet


text:
Of all the places I've visited in Tuscany, Siena is my favorite. There is just no boring corner in Siena. Everything around is a feast to the eyes. It's probably why it is the site of some famous movies, including James Bond, Quantum of Solace's horse race scene. It definitely is one of the loveliest places on earth. Read the full Siena and San Giminagno experience on escapecapades.com
|The pines, the vines and the olives... I really am in Tuscany!
I wouldn't mind visiting Siena again. :)


text:
Doane Paper Flap Jotter Review/
One of the good things about this space is that if you have a need, someone has probably had the same need at some point and filled it. The stationery community is full of creative people who, if they can't find what they want, dammit, they'll make it. One such person is Chad Doane of Doane Paper. The Grid + Lines ruling came from a meeting where half of the attendees were using lined paper, the other half graph paper. Originally just built as a downloadable pattern, fans liked the idea so much and clamored for an actual physical product. (Read the rest of the story here.)
This just goes to show that not ALL the great ideas have been done in stationery's long history. If anyone asked me why I keep trying new things and haven't settled, I'd say it's because new things keep coming out, there are new ideas to explore. One little tweak can turn an good notebook into a great one. I get so close, but then my needs change. There's never going to be a perfect notebook for everyone, but there may be one for you. If you can't find it, make it. That's what Doane did.
The product I'm looking at today is called the Large Flap Jotter on their site, but I'm just gonna called it the Jotter. This is a steno-style, top bound notebook with double wire-o binding. It's essentially a steno pad without being Gregg ruled. To be honest, it most reminds me of the Nock Co. spiral pad. It's very similar in size (5.5" x 8.5") and weight, even down to the fact that the covers are a little floppy. This one has been placed into the "next to the mouse" role on my desk, as I tend to use a top-bound book for that, usually in this size. I'll generally use it for throwaway notes or short task lists, writing out the steps of a larger task I plucked from my bullet journal to do. The book is perfect for this use case, for me.
That Brad Dowdy, the Pen Addict himself, loves this paper, is no surprise to me. The paper is a bit thinner and there is more show-through than I imagined, much like the Nock Co spiral pad. Rhodia this is not. It is not terrible paper, not in the slightest. But because Brad was such a proponent that he chose to use it for a ton of review, I would have thought it was great with fountain pens. Your gusher pens aren't gonna fare well, but if it doesn't bleed through normally, this paper will do pretty well with it. For pencil, this is solid. The paper is smooth, but not too much, and it won't shear down a pencil point like some toothier papers out there.
I find the cover a little weak. I wish that it had a heavier back. This style of notebook is meant to be held in hand and notes taken, and a lot of stenos have a heavier back cover card. It looks heavy to the eye, but don't let the pictures fool you. While it IS chipboard, it's thin. Hefty enough to protect the paper, but not really heavy enough to keep it straight. I can see why you may not want it that heavy, but to me, it's necessary for this style and size of steno pad.
Now, I touched on it above, but it's time to talk about the layout in depth. There are heavy lines for every 3 grid boxes. The grid squares are 1/8 of an inch. Compare that to a Field Notes grid, which is 3/16. So .125 vs .1875. The grid is too small for my tastes. It's the same dimensions as a Write Notepads standard graph or the Field Notes Utility engineering graph. So 3 of the boxes is one line of the ruling...which is 3/8 inch, or ~9.5mm. That is a super thick line. My preference is somewhere around the 7mm mark. I don't write small, but I definitely don't write that big either. If the lines are gonna be wide ruled, I'd like to see only 2 boxes inside. But if the grid size is more important, I'd like to see the lines be every other box, instead of every third. Essentially, my ideal Grid + Lines setup would be 3/16 inch boxes with every second line a bold line.
Regardless of my personal preference on the grid set up, the grid portion of the layout is light enough to straight up ignore, and I basically do. I use this as a lined book. The blue of the grid is light enough to fade behind most inks, but depending on the lightness of your pencil, the color may interfere. Most HBs are gonna be just fine, but you fans of the H and harder are probably going to want to steer clear, as the busy layout may compete with your light lines. I like people to know I've been there; soft smudgy pencils, thick gel pens, and wet liquid ink pens are my go-to, so I have no problem. The layout, while busy, is nowhere near as busy as the Nock Co Dot-Dash ruling, which the more I use the more I realize it's not for me.
Overall, this is a solid book. I've gotten the pocket notebooks as well, but have yet to use them. They have the same ruling, but I'm wondering if I'll be less picky once I'm using the Grid + Lines in a pocket-on-the-go setting as opposed to a desk setting. If you think you might want to try these, you should head over to Doane Paper and take a look at the offerings.
Available from Doane Paper, $9.