A variant of the Hales-Jewett theorem

It was shown by Bergelson that any set B with positive uppermultiplicative density contains nicely intertwined arithmeticand geometric progressions: for each k there exist a, b, d such that {b(a+id)^j: i, j {1, 2, ..., k}}B. In particular,one cell of each finite partition of contains such configurations.We prove a Hales–Jewett-type extension of this partitiontheorem.     

A density version of the Hales-Jewett theorem

Research supported by the National Science Foundation under Grant No. DMS86-05098.     

Some applications of the Hales-Jewett theorem to field arithmetic

Let K be a field whose absolute Galois group is finitely generated. If K neither finite nor of characteristic 2, then every hyperelliptic curve over K with all of its Weierstrass points defined over K has infinitely many K-points. If, in addition, K is not an algebraic extension of a finite field, then every elliptic curve over K with all of its 2-torsion rational has infinite rank over K. These and similar results are deduced from the Hales-Jewett theorem.     

A relative interpolation theorem for infinitary universal Horn logic and its applications

In this paper we deal with infinitary universal Horn logic both with and without equality. First, we obtain a relative Lyndon-style interpolation theorem. Using this result, we prove a non-standard preservation theorem which contains, as a particular case, a Lyndon-style theorem on surjective homomorphisms in its Makkai-style formulation. Another consequence of the preservation theorem is a theorem on bimorphisms, which, in particular, provides a tool for immediate obtaining characterizations of infinitary universal Horn classes without equality from those with equality. From the theorem on surjective homomorphisms we also derive a non-standard Beth-style preservation theorem that yields a non-standard Beth-style definability theorem, according to which implicit definability of a relation symbol in an infinitary universal Horn theory implies its explicit definability by a conjunction of atomic formulas. We also apply our theorem on surjective homomorphisms, theorem on bimorphisms and definability theorem to algebraic logic for general propositional logic.     

On the polynomial Lindenstrauss theorem

Under certain hypotheses on the Banach space X, we show that the set of N-homogeneous polynomials from X to any dual space, whose Aron–Berner extensions are norm attaining, is dense in the space of all continuous N-homogeneous polynomials. To this end we prove an integral formula for the duality between tensor products and polynomials. We also exhibit examples of Lorentz sequence spaces for which there is no polynomial Bishop–Phelps theorem, but our results apply. Finally we address quantitative versions, in the sense of Bollobás, of these results.     

An approach to infinitary temporal proof theory

Aim of this work is to investigate from a proof-theoretic viewpoint a propositional and a predicate sequent calculus with an –type schema of inference that naturally interpret the propositional and the predicate until–free fragments of Linear Time Logic LTL respectively. The two calculi are based on a natural extension of ordinary sequents and of standard modal rules. We examine the pure propositional case (no extralogical axioms), the propositional and the first order predicate cases (both with a possibly infinite set of extralogical axioms). For each system we provide a syntactic proof of cut elimination and a proof of completeness.Supported by MIUR COFIN 02 Teoria dei Modelli e Teoria degli Insiemi, loro interazioni ed applicazioni.Supported by MIUR COFIN 02 PROTOCOLLO.Mathematics Subject Classification (2000):03B22, 03B45, 03F05     

An infinitary probability logic for type spaces

Type spaces in the sense of Harsanyi (1967/68) play an important role in the theory of games of incomplete information. They can be considered as the probabilistic analog of Kripke structures. By an infinitary propositional language with additional operators “individual i assigns probability at least α to” and infinitary inference rules, we axiomatize the class of (Harsanyi) type spaces. We prove that our axiom system is strongly sound and strongly complete. To the best of our knowledge, this is the very first strong completeness theorem for a probability logic with σ-additive probabilities. We show this by constructing a canonical type space whose states consist of all maximal consistent sets of formulas. Furthermore, we show that this canonical space is universal (i.e., a terminal object in the category of type spaces) and beliefs complete.     

A polynomial Hutton theorem with applications

Extending a classical linear result due to Hutton to a nonlinear setting, we prove that a continuous homogeneous polynomial between Banach spaces can be approximated by finite rank polynomials if and only if its adjoint can be approximated by finite rank linear operators. Among other consequences, we apply this result to generalize a classical result due to Aron and Schottenloher about the approximation property on spaces of polynomials and a recent result due to Çaliskan and Rueda about the quasi-approximation property on projective symmetric tensor products.     

An application of infinitary universal algebra to set theory

Dedicated to Bjarni Jónsson on the occasion of his 70th birthday     

A polynomial space proof of the Graham-Pollak theorem

This note describes a polynomial space proof of the Graham-Pollak theorem.     

Central limit theorem for polynomial forms. I

Institute of Mathematics and Cybernetics, Academy of Sciences of the Lithuanian SSR. Translated from Litovskii Matematicheskii Sbornik (Lietuvos Matematikos Rinkinys), Vol. 29, No. 2, pp. 266–289, April–June, 1989.     

Induced lines in Hales-Jewett cubes

A line in d[n] is a set {x(1),…,x(n)} of n elements of d[n] such that for each 1?i?d, the sequence is either strictly increasing from 1 to n, or strictly decreasing from n to 1, or constant. How many lines can a set S⊆d[n] of a given size contain?One of our aims in this paper is to give a counterexample to the Ratio Conjecture of Patashnik, which states that the greatest average degree is attained when S=d[n]. Our other main aim is to prove the result (which would have been strongly suggested by the Ratio Conjecture) that the number of lines contained in S is at most |S|^2−ε for some ε>0.We also prove similar results for combinatorial, or Hales-Jewett, lines, i.e. lines such that only strictly increasing or constant sequences are allowed.     

Intersective polynomials and the polynomial Szemerédi theorem

Let be a family of polynomials such that , i=1,…,r. We say that the family P has the PSZ property if for any set with there exist infinitely many such that E contains a polynomial progression of the form {a,a+p₁(n),…,a+p_r(n)}. We prove that a polynomial family P={p₁,…,p_r} has the PSZ property if and only if the polynomials p₁,…,p_r are jointly intersective, meaning that for any there exists such that the integers p₁(n),…,p_r(n) are all divisible by k. To obtain this result we give a new ergodic proof of the polynomial Szemerédi theorem, based on the fact that the key to the phenomenon of polynomial multiple recurrence lies with the dynamical systems defined by translations on nilmanifolds. We also obtain, as a corollary, the following generalization of the polynomial van der Waerden theorem: If are jointly intersective integral polynomials, then for any finite partition of , there exist i{1,…,k} and a,nE_i such that {a,a+p₁(n),…,a+p_r(n)}E_i.