Maps on Ultrametric Spaces,Hensel's Lemma,and Differential Equations Over Valued Fields

We give a criterion for maps on ultrametric spaces to be surjective and to preserve spherical completeness. We show how Hensel's Lemma and the multidimensional Hensel's Lemma follow from our result. We give an easy proof that the latter holds in every henselian field. We also prove a basic infinite-dimensional Implicit Function Theorem. Further, we apply the criterion to deduce various versions of Hensel's Lemma for polynomials in several additive operators, and to give a criterion for the existence of integration and solutions of certain differential equations on spherically complete valued differential fields, for both valued D-fields in the sense of Scanlon, and differentially valued fields in the sense of Rosenlicht. We modify the approach so that it also covers logarithmic-exponential power series fields. Finally, we give a criterion for a sum of spherically complete subgroups of a valued abelian group to be spherically complete. This in turn can be used to determine elementary properties of power series fields in positive characteristic.     

Gauss’ lemma and valuation theory

Gauss’ lemma is not only critically important in showing that polynomial rings over unique factorization domains retain unique factorization; it unifies valuation theory. It figures centrally in Krull’s classical construction of valued fields with pre-described value groups, and plays a crucial role in our new short proof of the Ohm-Ja?ard-Kaplansky theorem on Bezout domains with given lattice-ordered abelian groups. Furthermore, Eisenstein’s criterion on the irreducibility of polynomials as well as Chao’s beautiful extension of Eisenstein’s criterion over arbitrary domains, in particular over Dedekind domains, are also obvious consequences of Gauss’ lemma. We conclude with a new result which provides a Gauss’ lemma for Hermite rings.     

Extremal results in sparse pseudorandom graphs

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.     

On factoring parametric multivariate polynomials

This paper presents a new algorithm for the absolute factorization of parametric multivariate polynomials over the field of rational numbers. This algorithm decomposes the parameters space into a finite number of constructible sets. The absolutely irreducible factors of the input parametric polynomial are given uniformly in each constructible set. The algorithm is based on a parametric version of Hensel's lemma and an algorithm for quantifier elimination in the theory of algebraically closed field in order to reduce the problem of finding absolute irreducible factors to that of representing solutions of zero-dimensional parametric polynomial systems. The complexity of this algorithm is single exponential in the number n of the variables of the input polynomial, its degree d w.r.t. these variables and the number r of the parameters.     

Permutation polynomials over finite fields from a powerful lemma

Using a lemma proved by Akbary, Ghioca, and Wang, we derive several theorems on permutation polynomials over finite fields. These theorems give not only a unified treatment of some earlier constructions of permutation polynomials, but also new specific permutation polynomials over Fq. A number of earlier theorems and constructions of permutation polynomials are generalized. The results presented in this paper demonstrate the power of this lemma when it is employed together with other techniques.     

Irreducible values of polynomials

Schinzel's Hypothesis H is a general conjecture in number theory on prime values of polynomials that generalizes, e.g., the twin prime conjecture and Dirichlet's theorem on primes in arithmetic progression. We prove a quantitative arithmetic analog of this conjecture for polynomial rings over pseudo algebraically closed fields. This implies results over large finite fields via model theory. A main tool in the proof is an irreducibility theorem à la Hilbert.     

The Matrix-Valued Riesz Lemma and Local Orthonormal Bases in Shift-Invariant Spaces

We use the matrix-valued Fejér–Riesz lemma for Laurent polynomials to characterize when a univariate shift-invariant space has a local orthonormal shift-invariant basis, and we apply the above characterization to study local dual frame generators, local orthonormal bases of wavelet spaces, and MRA-based affine frames. Also we provide a proof of the matrix-valued Fejér–Riesz lemma for Laurent polynomials.     

An algorithmic hypergraph regularity lemma

Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.     

Some Special Tauberian Theorems for Fourier Type Integrals and Eigenfunction Expansions of Sturm-Liouville Equations on the Whole Line

We offer a new proof of a special Tauberian theorem for Fourier type integrals. This Tauberian theorem was already considered by us in the papers [1] and [2]. The idea of our initial proof was simple, but the details were complicated because we used Bochner's definition of generalized Fourier transform for functions of polynomial growth. In the present paper we work with L. Schwartz's generalization. This leads to significant simplification. The paper consists of six sections. In Section 1 we establish an integral representation of functions of polynomial growth (subjected to some Tauberian conditions), in Section 2 we prove our main Tauberian theorems (Theorems 2.1 and 2.2.), using the integral representation of Section 1, in Section 3 we study the asymptotic behavior of M. Riesz's means of functions of polynomial growth, in Sections 4 and 5 we apply our Tauberian theorems to the problem of equiconvergence of eigenfunction expansions of Sturm-Liouville equations and expansion in ordinary Fourier integrals, and in Section 6 we compare our general equiconvergence theorems of Sections 4 and 5 with the well known theorems on eigenfunction expansions in classical orthogonal polynomials. In some sense this paper is a re-made survey of our results obtained during the period 1953-58. Another proof of our Tauberian theorem and some generalization can be found in the papers [3] and [4].     

Approximation for Frobenius algebraic equations in Witt vectors

We prove an approximation property for solutions to difference equations in excellent discrete valuation rings satisfying an appropriate Hensel's lemma, analog to a theorem of Greenberg [M. Greenberg, Rational points in henselian discrete valuation rings, Publ. Math. Inst. Hautes Études Sci. 31 (1966) 59–64]. In the case of Witt vectors we obtain a Nullstellensatz for Frobenius algebraic equations.     

A new proof of Fitzgerald's characterization of primitive polynomials

We give a new proof of Fitzgerald's criterion for primitive polynomials over a finite field. Existing proofs essentially use the theory of linear recurrences over finite fields. Here, we give a much shorter and self-contained proof which does not use the theory of linear recurrences.     

A note on Arzela–Ascoli's lemma in almost periodic problems

This paper is concerned with a generalized Arzela–Ascoli's lemma, which has been extensively applied in almost periodic problems by the continuation theorem of degree theory. We give a counter example to show that this lemma is incorrect, and there is a gap in the proof of some existing literature, where the addressed generalized Arzela–Ascoli's lemma was used. Moreover, we make some final comments and introduce an open problem. Copyright © 2016 John Wiley & Sons, Ltd.     

Book Ramsey numbers. I

A book B_p is a graph consisting of p triangles sharing a common edge. In this paper we prove that if p ≤ q/6 ?o(q) and q is large, then the Ramsey number r (B_p,B_q) is given by r (B_p,B_q) = 2q+3, and the constant 1/6 is essentially best possible. Our proof is based on Szemerédi's uniformity lemma and a stability result for books. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

An alternative proof of lower bounds for the first eigenvalue on manifolds

Recently, Andrews and Clutterbuck [1] gave a new proof of the optimal lower eigenvalue bound on manifolds via modulus of continuity for solutions of the heat equation. In this short note, we give an alternative proof of Theorem 2 in [1]. More precisely, following Ni's method (Section 6 of [5]), we give an elliptic proof of this theorem.     

Domain decomposition methods for CAD

Constructive solid geometry (CSG) in CAD leads to Domain decompositions which are based on primitive shapes, as briefly explained in the introduction below. A special role is played by “holes”, which can be viewed in several different ways. We combine this remark with the method of s. In a previous. In a previous note [7] where this method was introduced, the distributions resulting from the decomposition and Green's formula where thought of as virtual controls — here the virtual controls are introduced a priori with s, or itoutside the, or e the do the domain, or in the intersections of the domains. They are then chosen so as to (approximately) satisfy the Boundary conditions, which is possible by virtue of s (which have to be proven!). These (which have to be proven!). These ideas are presented here on an example (Section 1) which is certainly not the most general one but which is sufficient to show how everything extends to very many other situations. Algorithms, following the Approximate controllability lemma, are given in Section 2 and a numerical example is presented in Section 4.     

最值理论中一个结论的证明

同济大学《高等数学》最值理论中有结论称“若一个函数在一个区间内可导且只有一个驻点,并且这个驻点是函数的极值点,那么此驻点也是该函数的最值点”,但并未给出证明。学生们对此频感好奇。受Fermat引理启发,利用反证法可获一个比此结论更为一般的定理。     

On Farkas' lemma and related propositions in BISH

In this paper we analyse in the framework of constructive mathematics (BISH) the validity of Farkas' lemma and related propositions, namely the Fredholm alternative for solvability of systems of linear equations, optimality criteria in linear programming, Stiemke's lemma and the Superhedging Duality from mathematical finance, and von Neumann's minimax theorem with application to constructive game theory.     

A variant of the hypergraph removal lemma

Recent work of Gowers [T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001) 465-588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299-345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275-291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes.     

A local-global principle for linear dependence of noncommutative polynomials

A set of polynomials in noncommuting variables is called locally linearly dependent if their evaluations at tuples of matrices are always linearly dependent. By a theorem of Camino, Helton, Skelton and Ye, a finite locally linearly dependent set of polynomials is linearly dependent. In this short note an alternative proof based on the theory of polynomial identities is given. The method of the proof yields generalizations to directional local linear dependence and evaluations in general algebras over fields of arbitrary characteristic. A main feature of the proof is that it makes it possible to deduce bounds on the size of the matrices where the (directional) local linear dependence needs to be tested in order to establish linear dependence.