Monadic MV-algebras I: a study of subvarieties

In this paper, we study and classify some important subvarieties of the variety of monadic MV-algebras. We introduce the notion of width of a monadic MV-algebra and we prove that the equational class of monadic MV-algebras of finite width k is generated by the monadic MV-algebra [0, 1] ^k . We describe completely the lattice of subvarieties of the subvariety ${\mathcal{V}([{\bf 0}, {\bf 1}]^k)}$ generated by [0, 1] ^k . We prove that the subvariety generated by a subdirectly irreducible monadic MV-algebra of finite width depends on the order and rank of ?A, the partition associated to A of the set of coatoms of the boolean subalgebra B(A) of its complemented elements, and the width of the algebra. We also give an equational basis for each proper subvariety in ${\mathcal{V}([{\bf 0}, {\bf 1}]^k)}$ . Finally, we give some results about subvarieties of infinite width.     

Extendability of Continuous Maps Is Undecidable

We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological spaces X and Y, a subspace A?X, and a (continuous) map f:A→Y, decide whether f can be extended to a continuous map $\bar{f}\colon X\to Y$ . All spaces are given as finite simplicial complexes, and the map f is simplicial. Recent positive algorithmic results, proved in a series of companion papers, show that for (k?1)-connected Y, k≥2, the extension problem is algorithmically solvable if the dimension of X is at most 2k?1, and even in polynomial time when k is fixed. Here we show that the condition $\mathop{\mathrm{dim}}\nolimits X\leq 2k-1$ cannot be relaxed: for $\mathop{\mathrm{dim}}\nolimits X=2k$ , the extension problem with (k?1)-connected Y becomes undecidable. Moreover, either the target space Y or the pair (X,A) can be fixed in such a way that the problem remains undecidable. Our second result, a strengthening of a result of Anick, says that the computation of π _k (Y) of a 1-connected simplicial complex Y is #P-hard when k is considered as a part of the input.     

The index of an algebraic variety

Let K be the field of fractions of a Henselian discrete valuation ring  ${{\mathcal {O}}_{K}}$ . Let X _K /K be a smooth proper geometrically connected scheme admitting a regular model $X/{{\mathcal {O}}_{K}}$ . We show that the index δ(X _K /K) of X _K /K can be explicitly computed using data pertaining only to the special fiber X _k /k of the model X. We give two proofs of this theorem, using two moving lemmas. One moving lemma pertains to horizontal 1-cycles on a regular projective scheme X over the spectrum of a semi-local Dedekind domain, and the second moving lemma can be applied to 0-cycles on an $\operatorname {FA} $ -scheme X which need not be regular. The study of the local algebra needed to prove these moving lemmas led us to introduce an invariant γ(A) of a singular local ring $(A, {\mathfrak {m}})$ : the greatest common divisor of all the Hilbert-Samuel multiplicities e(Q,A), over all ${\mathfrak {m}}$ -primary ideals Q in ${\mathfrak {m}}$ . We relate this invariant γ(A) to the index of the exceptional divisor in a resolution of the singularity of $\operatorname {Spec}A$ , and we give a new way of computing the index of a smooth subvariety X/K of ${\mathbb{P}}^{n}_{K}$ over any field K, using the invariant γ of the local ring at the vertex of a cone over X.     

f-Vectors Implying Vertex Decomposability

We prove that if a pure simplicial complex $\Delta $ of dimension $d$ with $n$ facets has the least possible number of $(d-1)$ -dimensional faces among all complexes with $n$ faces of dimension $d$ , then it is vertex decomposable. This answers a question of J. Herzog and T. Hibi. In fact, we prove a generalization of their theorem using combinatorial methods.     

Cyclic symmetry of the scaled simplex

Let $\mathcal{Z}_{m}^{k}$ consist of the m ^k alcoves contained in the m-fold dilation of the fundamental alcove of the type A _k affine hyperplane arrangement. As the fundamental alcove has a cyclic symmetry of order k+1, so does $\mathcal{Z}_{m}^{k}$ . By bijectively exchanging the natural poset structure of $\mathcal{Z}_{m}^{k}$ for a natural cyclic action on a set of words, we prove that $(\mathcal{Z}_{m}^{k},\prod_{i=1}^{k} \frac{1-q^{m i}}{1-q^{i}},C_{k+1})$ exhibits the cyclic sieving phenomenon.     

On Σ-subsets of naturals over abelian groups

We obtain conditions for the Σ-definability of a subset of the set of naturals in the hereditarily finite admissible set over a model and for the computability of a family of such subsets. We prove that: for each e-ideal I there exists a torsion-free abelian group A such that the family of e-degrees of Σ-subsets of ω in $\mathbb{H}\mathbb{F}(A)$ coincides with I; there exists a completely reducible torsion-free abelian group in the hereditarily finite admissible set over which there exists no universal Σ-function; for each principal e-ideal I there exists a periodic abelian group A such that the family of e-degrees of Σ-subsets of ω in $\mathbb{H}\mathbb{F}(A)$ coincides with I.     

Algebraic equations on the adèlic closure of a Drinfeld module

Let k be a field of positive characteristic and K = k(V) a function field of a variety V over k and let A _K be the ring of adèles of K with respect to the places on K corresponding to the divisors on V. Given a Drinfeld module $\Phi :\mathbb{F}[t] \to End_K (\mathbb{G}_a )$ over K and a positive integer g we regard both K ^g and A _K ^g as $\Phi \left( {\mathbb{F}_p [t]} \right)$ -modules under the diagonal action induced by Φ. For Γ ? K ^g a finitely generated $\Phi \left( {\mathbb{F}_p [t]} \right)$ -submodule and an affine subvariety $X \subseteq \mathbb{G}_a^g$ defined over K, we study the intersection of X(A _K ), the adèlic points of X, with $\bar \Gamma$ , the closure of Γ with respect to the adèlic topology, showing under various hypotheses that this intersection is no more than X(K) ∩ Γ.     

Dense Arbitrarily Vertex Decomposable Graphs

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n ₁, . . . , n _k ) of positive integers such that n ₁ + · · · + n _k = n there exists a partition (V ₁, . . . , V _k ) of the vertex set of G such that for each ${i \in \{1,\ldots,k\}}$ , V _i induces a connected subgraph of G on n _i vertices. The main result of the paper reads as follows. Suppose that G is a connected graph on n ≥ 20 vertices that admits a perfect matching or a matching omitting exactly one vertex. If the degree sum of any pair of nonadjacent vertices is at least n ? 5, then G is arbitrarily vertex decomposable. We also describe 2-connected arbitrarily vertex decomposable graphs that satisfy a similar degree sum condition.     

Projective Hausdorff gaps

Todor?evi? (Fund Math 150(1):55–66, 1996) shows that there is no Hausdorff gap (A, B) if A is analytic. In this note we extend the result by showing that the assertion “there is no Hausdorff gap (A, B) if A is coanalytic” is equivalent to “there is no Hausdorff gap (A, B) if A is ${{\bf \it{\Sigma}}^{1}_{2}}$ ”, and equivalent to ${\forall r \; (\aleph_1^{L[r]}\,< \aleph_1)}$ . We also consider real-valued games corresponding to Hausdorff gaps, and show that ${\mathsf{AD}_\mathbb{R}}$ for pointclasses Γ implies that there are no Hausdorff gaps (A, B) if ${{\it{A}} \in {\bf \it{\Gamma}}}$ .     

Signed total (k, k)-domatic number of digraphs

Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → {?1, 1} be a two-valued function. If k ≥?1 is an integer and ${\sum_{x \in N^-(v)}f(x) \ge k}$ for each ${v \in V(G)}$ , where N ^?(v) consists of all vertices of D from which arcs go into v, then f is a signed total k-dominating function on D. A set {f ₁, f ₂, . . . , f _d } of signed total k-dominating functions on D with the property that ${\sum_{i=1}^df_i(x)\le k}$ for each ${x \in V(D)}$ , is called a signed total (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed total (k, k)-dominating family on D is the signed total (k, k)-domatic number on D, denoted by ${d_{st}^{k}(D)}$ . In this paper we initiate the study of the signed total (k, k)-domatic number of digraphs, and we present different bounds on ${d_{st}^{k}(D)}$ . Some of our results are extensions of known properties of the signed total domatic number ${d_{st}(D)=d_{st}^{1}(D)}$ of digraphs D as well as the signed total domatic number d _st (G) of graphs G, given by Henning (Ars Combin. 79:277–288, 2006).     

Invertible Factorization over Multiplier Algebras

Let ${\mathcal{A}}$ denote the multiplier algebra of an E-valued reproducing kernel Hilbert space, ${H_E^2(k)}$ . Then when H ²(k) is nice, we give necessary and sufficient conditions that T > 0 factors as A*A, where A and ${A^{-1} \in \mathcal{A}}$ . Such nice spaces include the Bergman and Hardy spaces on the unit polydisk and unit ball in ${\mathbb{C}^d}$ .     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

Asymptotic analysis of a second-order singular perturbation model for phase transitions

We study the asymptotic behavior, as ${\varepsilon}$ tends to zero, of the functionals ${F^k_\varepsilon}$ introduced by Coleman and Mizel in the theory of nonlinear second-order materials; i.e., $$F^k_\varepsilon(u):=\int\limits_{I} \left(\frac{W(u)}{\varepsilon}-k\,\varepsilon\,(u')^2+\varepsilon^3(u'')^2\right)\,dx,\quad u\in W^{2,2}(I),$$ where k?>?0 and ${W:\mathbb{R}\to[0,+\infty)}$ is a double-well potential with two potential wells of level zero at ${a,b\in\mathbb{R}}$ . By proving a new nonlinear interpolation inequality, we show that there exists a positive constant k ₀ such that, for k?<?k ₀, and for a class of potentials W, ${(F^k_\varepsilon)}$ ??(L ¹)-converges to $$F^k(u):={\bf m}_k \, \#(S(u)),\quad u\in BV(I;\{a,b\}),$$ where m _k is a constant depending on W and k. Moreover, in the special case of the classical potential ${W(s)=\frac{(s^2-1)^2}{2}}$ , we provide an upper bound on the values of k such that the minimizers of ${F_\varepsilon^k}$ cannot develop oscillations on some fine scale and a lower bound on the values for which oscillations occur, the latter improving a previous estimate by Mizel, Peletier and Troy.     

Generalized absolute Hausdorff summability of orthogonal series

For 1≦k≦2 and a sequence $\gamma :={\{\gamma(n)\}}_{n=1}^{\infty}$ that is quasi β-power monotone decreasing with ${\beta>1-\frac{1}{k}}$ , we prove the |A,γ| _k summability of an orthogonal series, where A is either a regular or Hausdorff matrix. For ${\beta>-\frac{3}{4}}$ , we give a necessary and sufficient condition for |A,γ| _k summability, where A is Hausdorff matrix. Our sufficient condition for ${\beta>-\frac{3}{4}}$ is weaker than that of Kantawala [1], ${\beta>-\frac{1}{k}}$ for |E,q,γ| _k summability; and of Leindler [4], β>?1 for |C,α,γ| _k , ${\alpha<\frac{1}{4}}$ . Also, our result generalizes the result of Spevakov [6] for |E,q,1|₁ summability.     

Cone Dependence—A Basic Combinatorial Concept

We call A ? $ \mathbb{E} $ ⁿ cone independent of B ? $ \mathbb{E} $ ⁿ , the euclidean n-space, if no a = (a ₁,..., a _n ) ∈ A equals a linear combination of B \ {a} with non-negative coefficients. If A is cone independent of A we call A a cone independent set. We begin the analysis of this concept for the sets P(n) = {A ? {0, 1} ⁿ ? $ \mathbb{E} $ ⁿ : A is cone independent} and their maximal cardinalities c(n) ? max{|A| : A ∈ P(n)}. We show that lim _{n → ∞} $ \frac{{c\left( n \right)}}{{2^n }} $ > $\frac{1}{2}$ , but can't decide whether the limit equals 1. Furthermore, for integers 1 < k < ? ≤ n we prove first results about c _n (k, ?) ? max{|A| : A ∈ P _n (k, ?)}, where P _n (k, ?) = {A : A ? V ⁿ _k and V ⁿ _? is cone independent of A} and V ⁿ _k equals the set of binary sequences of length n and Hamming weight k. Finding c _n (k, ?) is in general a very hard problem with relations to finding Turan numbers.     

A Short Note on Essentially Σ1 Sentences

Guaspari (J Symb Logic 48:777–789, 1983) conjectured that a modal formula is it essentially Σ₁ (i.e., it is Σ₁ under any arithmetical interpretation), if and only if it is provably equivalent to a disjunction of formulas of the form ${\square{B}}$ . This conjecture was proved first by A. Visser. Then, in (de Jongh and Pianigiani, Logic at Work: In Memory of Helena Rasiowa, Springer-Physica Verlag, Heidelberg-New York, pp. 246–255, 1999), the authors characterized essentially Σ₁ formulas of languages including witness comparisons using the interpretability logic ILM. In this note we give a similar characterization for formulas with a binary operator interpreted as interpretability in a finitely axiomatizable extension of IΔ ₀  + Supexp and we address a similar problem for IΔ ₀  + Exp.     

Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.     

Iterated vanishing cycles

If A ^? is a bounded, constructible complex of sheaves on a complex analytic space X, and ${f : X \rightarrow \mathbb{C}}$ and ${g : X \rightarrow \mathbb{C}}$ are complex analytic functions, then the iterated vanishing cycles φ _g [?1](φ _f [?1]A ^?) are important for a number of reasons. We give a formula for the stalk cohomology H*(φ _g [?1]φ _f [?1]A ^?) _x in terms of relative polar curves, algebra, and Morse modules of A ^?.     

Estimates related to sumfree subsets of sets of integers

A subsetA of the positive integers ?₊ is called sumfree provided (A+A)∩A=ø. It is shown that any finite subsetB of ?₊ contains a sumfree subsetA such that |A|≥1/3(|B|+2), which is a slight improvement of earlier results of P. Erdös [Erd] and N. Alon-D. Kleitman [A-K]. The method used is harmonic analysis, refining the original approach of Erdös. In general, defines _k (B) as the maximum size of ak-sumfree subsetA ofB, i.e. (A) _k = $\underbrace {A + ... + A}_{k times}$ % MathType!End!2!1! is disjoint fromA. Elaborating the techniques permits one to prove that, for instance, $s_3 \left( B \right) > \frac{{\left| B \right|}}{4} + c\frac{{\log \left| B \right|}}{{\log \log \left| B \right|}}$ % MathType!End!2!1!as an improvement of the estimate $s_k \left( B \right) > \frac{{\left| B \right|}}{4}$ % MathType!End!2!1! resulting from Erdös’ argument. It is also shown that in an inequalitys _k (B)>δ _k |B|, valid for any finite subsetB of ?₊, necessarilyδ _k → 0 fork → ∞ (which seemed to be an unclear issue). The most interesting part of the paper are the methods we believe and the resulting harmonic analysis questions. They may be worthwhile to pursue.