Equivalence in Finite-Variable Logics is Complete for Polynomial Time

of first-order logic whose formulas contain at most k variables (for some ). We show that for each , equivalence in the logic is complete for polynomial time. Moreover, we show that the same completeness result holds for the powerful extension of with counting quantifiers (for every ). The k-dimensional Weisfeiler–Lehman algorithm is a combinatorial approach to graph isomorphism that generalizes the naive color-refinement method (for ). Cai, Fürer and Immerman [6] proved that two finite graphs are equivalent in the logic if, and only if, they can be distinguished by the k-dimensional Weisfeiler-Lehman algorithm. Thus a corollary of our main result is that the question of whether two finite graphs can be distinguished by the k-dimensional Weisfeiler–Lehman algorithm is P-complete for each . Received: March 23, 1998     

The two‐variable fragment with counting and equivalence

We consider the two‐variable fragment of first‐order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime ‐complete. We further show that the corresponding problems for two‐variable first‐order logic with counting and two equivalences are both undecidable.     

An optimal lower bound on the number of variables for graph identification

In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308.     

Axiomatization and Polynomial Solvability of Strictly Positive Fragments of Certain Modal Logics

The fragment of the language of modal logic that consists of all implications A → B, where A and B are built from variables, the constant ⊤ (truth), and the connectives ∧ and ◊₁,◊₂,...,◊ _m . For the polymodal logic S5 _m (the logic of m equivalence relations) and the logic K4.3 (the logic of irreflexive linear orders), an axiomatization of such fragments is found and their algorithmic decidability in polynomial time is proved.

     

On Heisenberg-like Super Group Structures

The ring-like structures that can be defined on the ground supermanifolds \mathbb R^1|1{\mathbb R^{1\vert 1}} and \mathbb C^1|1{\mathbb C^{1\vert 1}} are classified up to equivalence in the category of smooth and complex Berezin-Kostant-Leites-Manin supermanifolds. It is proved that there are three different such equivalence classes in the real case, whereas there are two for the complex field. The corresponding module structures—defined componentwise on the product of k copies of \mathbb R^1|1{\mathbb R^{1\vert 1}} or \mathbb C^1|1{\mathbb C^{1\vert 1}}—are also classified up to equivalence. The notions of linearity and bilinearity are reviewed and used to define Heisenberg-like super group structures. It turns out that there are three non-isomorphic real such super groups, whereas only two over the complex field. The use of the appropriate exponential maps introduces the possibility of defining Heisenberg-like super group structures on the product of k copies of the ground supermanifold, with an appropriate super circle. The corresponding classification is also obtained.     

Cross-sections, quotients, and representation rings of semisimple algebraic groups

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny t:[^(G)] ? G \tau :\hat{G} \to G is bijective; this answers Grothendieck’s question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg’s theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G] ^G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G] ^G and that of the representation ring of G and answer two Grothendieck’s questions on constructing generating sets of k[G] ^G . We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T ⇢ G/T where T is a maximal torus of G and W the Weyl group.     

Multicolor containers,extremal entropy,and counting

In breakthrough results, Saxton‐Thomason and Balogh‐Morris‐Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simple container theorem of Saxton‐Thomason and an entropy‐based framework to deduce container and counting theorems for hereditary properties of k‐colorings of very general objects, which include both vertex‐ and edge‐colorings of general hypergraph sequences as special cases. In the case of sequences of complete graphs, we further derive characterization and transference results for hereditary properties in terms of their stability families and extremal entropy. This covers within a unified framework a great variety of combinatorial structures, some of which had not previously been studied via containers: directed graphs, oriented graphs, tournaments, multigraphs with bounded multiplicity, and multicolored graphs among others. Similar results were recently and independently obtained by Terry.     

The ultra‐weak Ash conjecture and some particular cases

Ash's functions N _{σ ,k} count the number of k ‐equivalence classes of σ ‐structures of size n . Some conditions on their asymptotic behavior imply the long standing spectrum conjecture. We present a new condition which is equivalent to this conjecture and we discriminate some easy and difficult particular cases. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)

Many applications call for exhaustive lists of strings subject to various constraints, such as inequivalence under group actions. A k-ary necklace is an equivalence class of k-ary strings under rotation (the cyclic group). A k-ary unlabeled necklace is an equivalence class of k-ary strings under rotation and permutation of alphabet symbols. We present new, fast, simple, recursive algorithms for generating (i.e., listing) all necklaces and binary unlabeled necklaces. These algorithms have optimal running times in the sense that their running times are proportional to the number of necklaces produced. The algorithm for generating necklaces can be used as the basis for efficiently generating many other equivalence classes of strings under rotation and has been applied to generating bracelets, fixed density necklaces, and chord diagrams. As another application, we describe the implementation of a fast algorithm for listing all degree n irreducible and primitive polynomials over GF(2).     

Joint distributions of numbers of success-runs and failures until the first consecutivek successes

Joint distributions of the numbers of failures, successes and success-runs of length less thank until the first consecutivek successes are obtained for some random sequences such as a sequence of independent and identically distributed integer valued random variables, a {0, 1}-valued Markov chain and a binary sequence of orderk. There are some ways of counting numbers of runs with a specified length. This paper studies the joint distributions based on three ways of counting numbers of runs, i.e., the number of overlapping runs with a specified length, the number of non-overlapping runs with a specified length and the number of runs with a specified length or more. Marginal distributions of them can be derived immediately, and most of them are surprisingly simple.This research was partially supported by the ISM Cooperative Research Program (93-ISM-CRP-8).     

On the complexity of axiomatizations of the class of representable quasi‐polyadic equality algebras

Using games, as introduced by Hirsch and Hodkinson in algebraic logic, we give a recursive axiomatization of the class RQPEA _α of representable quasi‐polyadic equality algebras of any dimension α. Following Sain and Thompson in modifying Andréka’s methods of splitting, to adapt the quasi‐polyadic equality case, we show that if Σ is a set of equations axiomatizing RPEA _n for $2< n <\omegaUsing games, as introduced by Hirsch and Hodkinson in algebraic logic, we give a recursive axiomatization of the class RQPEA _α of representable quasi‐polyadic equality algebras of any dimension α. Following Sain and Thompson in modifying Andréka’s methods of splitting, to adapt the quasi‐polyadic equality case, we show that if Σ is a set of equations axiomatizing RPEA _n for $2< n <\omega$ and $l< n,$ $k < n$, k′ < ω are natural numbers, then Σ contains infinitely equations in which ? occurs, one of + or · occurs, a diagonal or a permutation with index l occurs, more than k cylindrifications and more than k′ variables occur. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Poisson convergence in the restricted k‐partitioning problem

The randomized k‐number partitioning problem is the task to distribute N i.i.d. random variables into k groups in such a way that the sums of the variables in each group are as similar as possible. The restricted k‐partitioning problem refers to the case where the number of elements in each group is fixed to N/k. In the case k = 2 it has been shown that the properly rescaled differences of the two sums in the close to optimal partitions converge to a Poisson point process, as if they were independent random variables. We generalize this result to the case k > 2 in the restricted problem and show that the vector of differences between the k sums converges to a k ‐ 1‐dimensional Poisson point process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On cubic polynomials I. Hua's estimate of exponential sums

Hua andChen gave estimates of sums wheree(z)=e ^2iz and is a polynomial of the typef(x)/q wheref(x)=a _k x ^k +...+a ₁ x with integer coefficients having gcd (q, a _k ,...,a ₁)=1 But no good estimates hold for these sums whenq is small in comparison tok. We therefore consider here a related but different class of polynomials. Special emphasis is given to the cubic case.In subsequent papers of this series we shall deal with cubic exponential sums in many variables and withp-adic and rational zeros of systems of cubic forms.Partially supported by NSF contract NSF-MCS-8015356.     

On energy estimates for second order hyperbolic equations with Levi conditions for higher order regularity

We consider energy estimates for second order homogeneous hyperbolic equations with time dependent coefficients. The property of energy conservation, which holds in the case of constant coefficients, does not hold in general for variable coefficients; in fact, the energy can be unbounded as t → ∞ in this case. The conditions to the coefficients for the generalized energy conservation (GEC), which is an equivalence of the energy uniformly with respect to time, has been studied precisely for wave type equations, that is, only the propagation speed is variable. However, it is not true that the same conditions to the coefficients conclude (GEC) for general homogeneous hyperbolic equations. The main purpose of this paper is to give additional conditions to the coefficients which provide (GEC); they will be called as C ^k -type Levi conditions due to the essentially same meaning of usual Levi condition for the well-posedness of weakly hyperbolic equations.     

Affine equivalence for rotation symmetric Boolean functions with 2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript> variables

Rotation symmetric Boolean functions have been extensively studied in the last 10 years or so because of their importance in cryptography and coding theory. Until recently, very little was known about the basic question of when two such functions are affine equivalent. Even the case of quadratic functions is nontrivial, and this was only completely settled in a 2009 paper of Kim, Park and Hahn. The much more complicated case of cubic functions was solved for permutations using a new concept of patterns in a 2010 paper of Cusick, and it is conjectured that, as in the quadratic case, this solution actually applies for all affine transformations. The patterns method enables a detailed analysis of the affine equivalence classes for various special classes of cubic rotation symmetric functions in n variables. Here the case of functions with 2 ^k variables (this number is especially relevant in computer applications) and generated by a single monomial is examined in detail, and in particular a formula for the number of classes is proved.     

The expressive power of k-ary exclusion logic

In this paper we study the expressive power of k-ary exclusion logic, EXC[k], that is obtained by extending first order logic with k-ary exclusion atoms. It is known that without arity bounds exclusion logic is equivalent with dependence logic. By observing the translations, we see that the expressive power of EXC[k] lies in between k-ary and ($k+1$)-ary dependence logics. We will show that, at least in the case when $k=1$, both of these inclusions are proper.In a recent work by the author it was shown that k-ary inclusion-exclusion logic is equivalent with k-ary existential second order logic, ESO[k]. We will show that, on the level of sentences, it is possible to simulate inclusion atoms with exclusion atoms, and in this way express ESO[k]-sentences by using only k-ary exclusion atoms. For this translation we also need to introduce a novel method for “unifying” the values of certain variables in a team. As a consequence, EXC[k] captures ESO[k] on the level of sentences, and we obtain a strict arity hierarchy for exclusion logic. It also follows that k-ary inclusion logic is strictly weaker than EXC[k].Finally we use similar techniques to formulate a translation from ESO[k] to k-ary inclusion logic with an alternative strict semantics. Consequently, for any arity fragment of inclusion logic, strict semantics is strictly more expressive than lax semantics.     

Convergence of types in k-space

Summary If random variables X _n converge in distribution to a nondegenerate random variable X, and if transformations a _n X _n +b _n of them, with a _n >0, also converge in distribution to X, then a _n 1 and b _n 0. Moreover, the group of transformations xax+b that preserve the distribution of a nondegenerate random variable consists either of the identity alone, or of the identity together with the reflection through some point. For proofs see [4], [5], or [6]. This paper gives the corresponding results for k-dimensional random vectors.This research was supported in part by Research Grant No. NSF-GP 3707 from the Division of Mathematical, Physical, and Engineering Sciences of the National Science Foundation.I should like thank Hans BrØns and SØren Johansen for very helpful discussions.     

Über Mittelwerte multiplikativer zahlentheoretischer Funktionen mehrerer Variablen

In [8] the author extended the concept of neighbouring functions (cp. [9]) to the case of several variables. Using these results it is shown that under some weak conditions a multiplicative functionf in two variables has a mean-value different from zero if and only if the two multiplicative functionsf ₁(n)=f(n, 1) andf ₂(n)=f(1,n) have mean-values different from zero. Applications to theorems ofDelange [3],Elliott [6] andDaboussi [1] are given.     

Some Remarks on the Definition of Boltzmann, Shannon and Kolmogorov Entropy

We give an alternative definition of Shannon and Kolmogorov-Sinai entropies based on the Boltzmann formula S = k log W. We prove the equivalence of those new definitions with the traditional ones using some tools from Information Theory such as information function and empirical entropy. Lecture held in the Seminario Matematico e Fisico on November 29, 2004 Received: April 2005     

A proof of Parisi’s conjecture on the random assignment problem

An assignment problem is the optimization problem of finding, in an m by n matrix of nonnegative real numbers, k entries, no two in the same row or column, such that their sum is minimal. Such an optimization problem is called a random assignment problem if the matrix entries are random variables. We give a formula for the expected value of the optimal k-assignment in a matrix where some of the entries are zero, and all other entries are independent exponentially distributed random variables with mean 1. Thereby we prove the formula 1+1/4+1/9+...+1/k ² conjectured by G. Parisi for the case k=m=n, and the generalized conjecture of D. Coppersmith and G. B. Sorkin for arbitrary k, m and n. AcknowledgementWe thank Mireille Bousquet-Mélou and Gilles Schaeffer for introducing the problem to us. We also thank an anonymous referee for suggesting some improvements of the exposition.