Axiomatizing Provable <Emphasis Type="Italic">n</Emphasis>-Provability

The set of all formulas whose n-provability in a given arithmetical theory S is provable in another arithmetical theory T is a recursively enumerable extension of S. We prove that such extensions can be naturally axiomatized in terms of transfinite progressions of iterated local reflection schemata over S. Specifically, the set of all provably 1-provable sentences in Peano arithmetic PA can be axiomatized by an ε₀-times iterated local reflection schema over PA. The resulting characterizations provide additional information on the proof-theoretic strength of these theories and on the complexity of their axiomatization.     

Arithmetic Progressions in Linear Combinations of <Emphasis Type="Italic">S</Emphasis>-Units

M. Pohst asked the following question: is it true that every prime can be written in the form 2^u ± 3^v with some non-negative integers u, v? We put the problem into a general framework, and prove that the length of any arithmetic progression in t-term linear combinations of elements from a multiplicative group of rank r (e.g. of S-units) is bounded in terms of r, t, n, where n is the number of the coefficient t-tuples of the linear combinations. Combining this result with a recent theorem of Green and Tao on arithmetic progressions of primes, we give a negative answer to the problem of M. Pohst.     

Maximal subsets free of arithmetic progressions in arbitrary sets

The problem of determining the maximum cardinality of a subset containing no arithmetic progressions of length k in a given set of size n is considered. It is proved that it is sufficient, in a certain sense, to consider the interval [1,..., n]. The study continues the work of Komlós, Sulyok, and Szemerédi.     

Finite Sets as Complements of Finite Unions of Convex Sets

Suppose S?? ^d is a set of (finite) cardinality n, whose complement can be written as the union of k convex sets. It is perhaps intuitively appealing that when n is large k must also be large. This is true, as is shown here. First the case in which the convex sets must also be open is considered, and in this case a family of examples yields an upper bound, while a simple application of a theorem of Björner and Kalai yields a lower bound. Much cruder estimates are then obtained when the openness restriction is dropped. For a given set S the problem of determining the smallest number of convex sets whose union is ? ^d ?S is shown to be equivalent to the problem of finding the chromatic number of a certain (infinite) hypergraph ? _S . We consider the graph \(\mathcal {G}_{S}\) whose edges are the 2-element edges of ? _S , and we show that, when d=2, for any sufficiently large set S, the chromatic number of \(\mathcal{G}_{S}\) will be large, even though there exist arbitrarily large finite sets S for which \(\mathcal{G}_{S}\) does not contain large cliques.     

On positive-influence target-domination

Consider a graph \(G=(V,E)\) and a vertex subset \(A \subseteq V\). A vertex v is positive-influence dominated by A if either v is in A or at least half the number of neighbors of v belong to A. For a target vertex subset \(S \subseteq V\), a vertex subset A is a positive-influence target-dominating set for target set S if every vertex in S is positive-influence dominated by A. Given a graph G and a target vertex subset S, the positive-influence target-dominating set (PITD) problem is to find the minimum positive-influence dominating set for target S. In this paper, we show two results: (1) The PITD problem has a polynomial-time \((1 + \log \lceil \frac{3}{2} \Delta \rceil )\)-approximation in general graphs where \(\Delta \) is the maximum vertex-degree of the input graph. (2) For target set S with \(|S|=\Omega (|V|)\), the PITD problem has a polynomial-time O(1)-approximation in power-law graphs.     

On a problem of impulse control under interference

This paper contains several results about the structure of the congruence kernel C^(S)(G) of an absolutely almost simple simply connected algebraic group G over a global field K with respect to a set of places S of K. In particular, we show that C^(S)(G)) is always trivial if S contains a generalized arithmetic progression. We also give a criterion for the centrality of C^(S)(G) in the general situation in terms of the existence of commuting lifts of the groups G(K_v) for v ? S in the S-arithmetic completion ?^(S). This result enables one to give simple proofs of the centrality in a number of cases. Finally, we show that if K is a number field and G is K-isotropic, then C^(S)(G) as a normal subgroup of ?^(S) is almost generated by a single element.     

Atomic subspaces of {L_1}-martingale spaces

In Part I of the present paper the following problem was investigated. Let G be a finite simple graph, and S be a finite set of primes. We say that G is representable with S if it is possible to attach rational numbers to the vertices of G such that the vertices v₁, v₂ are connected by an edge if and only if the difference of the attached values is an S-unit. In Part I we gave several results concerning the representability of graphs in the above sense.     

Arithmetic Progressions and Its Applications to (m,q)-Isometries: A Survey

In this paper we collect some results about arithmetic progressions of higher order, also called polynomial sequences. Those results are applied to (m, q)-isometric maps.     

Difference scheme for an initial–boundary value problem for a singularly perturbed transport equation

An initial–boundary value problem for a singularly perturbed transport equation with a perturbation parameter ε multiplying the spatial derivative is considered on the set ? = G ∪ S, where ? = D? × [0 ≤ t ≤ T], D? = {0 ≤ x ≤ d}, S = S ^l ∪ S, and S ^l and S₀ are the lateral and lower boundaries. The parameter ε takes arbitrary values from the half-open interval (0,1]. In contrast to the well-known problem for the regular transport equation, for small values of ε, this problem involves a boundary layer of width O(ε) appearing in the neighborhood of S ^l ; in the layer, the solution of the problem varies by a finite value. For this singularly perturbed problem, the solution of a standard difference scheme on a uniform grid does not converge ε-uniformly in the maximum norm. Convergence occurs only if h=dN^-1 ? ε and N₀^-1 ? 1, where N and N₀ are the numbers of grid intervals in x and t, respectively, and h is the mesh size in x. The solution of the considered problem is decomposed into the sum of regular and singular components. With the behavior of the singular component taken into account, a special difference scheme is constructed on a Shishkin mesh, i.e., on a mesh that is piecewise uniform in x and uniform in t. On such a grid, a monotone difference scheme for the initial–boundary value problem for the singularly perturbed transport equation converges ε-uniformly in the maximum norm at an ?(N^?1 + N₀^?1) rate.     

Cyclic gradings of Lie algebras and lax pairs for <Emphasis Type="Italic">σ</Emphasis>-models

We study a class of σ-models with complex homogeneous target spaces and zero-curvature representations. We find a relation between these models and σ-models with certain m-symmetric target spaces. We also describe a model with the hypercomplex target space S ¹ × S ³ in detail.     

Spectra of Automorphic Extensions of Finite Simple Exceptional Groups of Lie Type

The spectrum ω (G) of a finite group G is the set of orders of elements of G. Let S be a simple exceptional group of type E ₆ or E ₇ . We describe all finite groups G such that S ≤ G ≤ Aut S and ω (G) = ω (S) and completes the study of the recognition-by-spectrum problem for all simple exceptional groups of Lie type.     

On a conjecture of Bulman-Fleming and Gilmour

If S is a monoid, the set S×S equipped with componentwise S-action is called the diagonal act of S and is denoted by D(S). We prove the following theorem: the right S-act S ⁿ (1≠n∈?) is (principally) weakly flat if and only if \(\prod _{i=1}^{n}A_{i}\) is (principally) weakly flat where A _i , 1≤i≤n are (principally) weakly flat right S-acts, if and only if the diagonal act D(S) is (principally) weakly flat. This gives an answer to a conjecture posed by Bulman-Fleming and Gilmour (Semigroup Forum 79:298–314, 2009). Besides, we present a fair characterization of monoids S over which the diagonal act D(S) is (principally) weakly flat and finally, we impose a condition on D(S) in order to make S a left PSF monoid.     

Sasakian structures on CR-manifolds

A contact manifold M can be defined as a quotient of a symplectic manifold X by a proper, free action of \(\mathbb{R}\), with the symplectic form homogeneous of degree 2. If X is also Kähler, and its metric is homogeneous of degree 2, M is called Sasakian. A Sasakian manifold is realized naturally as a level set of a Kähler potential on a complex manifold, hence it is equipped with a pseudoconvex CR-structure. We show that any Sasakian manifold M is CR-diffeomorphic to an S ¹-bundle of unit vectors in a positive line bundle on a projective Kähler orbifold. This induces an embedding of M into an algebraic cone C. We show that this embedding is uniquely defined by the CR-structure. Additionally, we classify the Sasakian metrics on an odd-dimensional sphere equipped with a standard CR-structure.     

On <Emphasis Type="BoldItalic">S</Emphasis>-strong Mori modules

Let A be an integral domain, \(S\subseteq A\) be a multiplicative set and M a w-module as an A-module. In this paper we investigate S-SM-modules. We give an S-version of the result of Wang and McCasland (Commun Algebra 25:1285–1306, 1997) in the case where S is countable. We prove that M is an S-SM-module if and only if every increasing sequence of w-submodules of M is S-stationary if and only if every increasing sequence of S-w-finite w-submodules of M is S-stationary if and only if every increasing sequence of w-finite type submodules of M is S-stationary.     

Arithmetic progressions in multiplicative groups of finite fields

Let G be a multiplicative subgroup of the prime field F _p of size |G| > p^1?κ and r an arbitrarily fixed positive integer. Assuming κ = κ(r) > 0 and p large enough, it is shown that any proportional subset A ? G contains non-trivial arithmetic progressions of length r. The main ingredient is the Szemerédi–Green–Tao theorem.     

On countable unions of nonmeager sets in hereditarily Lindelöf spaces

It is well known that any Vitali set on the real line ? does not possess the Baire property. The same is valid for finite unions of Vitali sets. What can be said about infinite unions of Vitali sets? Let S be a Vitali set, S _r be the image of S under the translation of ? by a rational number r and F = {S _r : r is rational}. We prove that for each non-empty proper subfamily F′ of F the union ∪F′ does not possess the Baire property. We say that a subset A of ? possesses Vitali property if there exist a non-empty open set O and a meager set M such that A ? O \ M. Then we characterize those non-empty proper subfamilies F′ of F which unions ∪F′ possess the Vitali property.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Asymptotic behavior of the solution of a nonlinear integro-differential diffusion equation

We study the asymptotic behavior as t → ∞ of the solution of the initial-boundary value problem for the nonlinear integro-differential equation

$$\frac{{\partial U}}{{\partial t}} = \frac{\partial }{{\partial x}}\left[ {a\left( {\mathop \smallint \limits_0^t \left( {\frac{{\partial U}}{{\partial x}}} \right)^2 d\tau } \right)\frac{{\partial U}}{{\partial x}}} \right],$$

where a(S) = (1 + S) ^p , 0 < p ≤ 1. We consider problems with homogeneous boundary conditions as well as with a nonhomogeneous boundary condition on part of the boundary. The orders of convergence are established.

     

Finite configurations in sparse sets

Let E ? ?ⁿ be a closed set of Hausdorff dimension α. For m > n, let{B₁, …, B_k} be n × (m ? n) matrices. We prove that if the system of matrices B_j is non-degenerate in a suitable sense, α is sufficiently close to n, and if E supports a probability measure obeying appropriate dimensionality and Fourier decay conditions, then for a range of m depending on n and k, the set E contains a translate of a non-trivial k-point configuration {B₁y, …, B_ky}. As a consequence, we are able to establish existence of certain geometric configurations in Salem sets (such as parallelograms in ?ⁿ and isosceles right triangles in ?²). This can be viewed as a multidimensional analogue of the result of [25] on 3-term arithmetic progressions in subsets of ?.     

Plane Partitions and Their Pedestal Polynomials

For a linear extension P of a partially ordered set S, we consider a generating multivariate polynomial of certain reverse partitions on S, called P-pedestals. We establish a remarkable property of this polynomial: it does not depend on the choice of P. For S a Young diagram, we show that this polynomial generalizes the hook polynomial.