Convex subsets of 2n and bounded truth-table reducibility

Let 2ⁿ be the set of n-tuples of 0's and 1's, partially ordered componentwise. A characterization is given of the possible decompositions of arbitrary subsets of 2ⁿ as disjoint unions of sets which are convex in this ordering; this result is used to obtain a decomposition theorem for Boolean functions in terms of monotone functions. The second half of the paper contains applications to recursion theory; in particular, canonical forms for certain minimum-norm bounded-truth-table reductions are obtained.     

On representation of Stinespring’s type for n-tuples of completely positive maps in Hilbert C ⋆-modules

Here we prove an analog of the Stinespring’s theorem for n-tuples of completely positive maps in Hilbert C ^?-modules.     

A construction of orthogonal arrays and applications to embedding theorems

An n^t by k orthogonal array is a collection of k-tuples of elements from an n-set, such that if a matrix is formed with the k-tuples as rows then each ordered t-tuple of elements appears exactly once as a row of each t columned and n^t rowed submatrix. If such an array has its set of k-tuples invariant under the elements of a subgroup G of S_t then the array is referred to as a G-array. A method is described for constructing a G-array of order nr from an array of order n and G-arrays of order r.The above described construction is used to produce finite embedding theorems for partial 3-quasigroups of various types. For a class of 3-quasigroups, such a theorem shows that a finite partial member of the class can be embedded in a finite complete member of the class. Theorems included produce finite embedding theorems for 3-quasigroups satisfying the identities 〈x,y,〈y,x,z〉〉=z and 〈〈z,x,y〉,y,x〉=z, for cyclic 3-quasigroup s, and conditional embedding theorems are presented for semi-symmetric 3-quasigroups.     

Non-Trivial t-Intersection in the Function Lattice

The function lattice, or generalized Boolean algebra, is the set of ℓ-tuples with the ith coordinate an integer between 0 and a bound n_i. Two ℓ-tuples t-intersect if they have at least t common nonzero coordinates. We prove a Hilton–Milner type theorem for systems of t-intersecting ℓ-tuples.Received September 29, 2004     

A joint similarity problem for n-tuples of operators on vector-valued Bergman spaces

We investigate n-tuples of commuting Foias-Williams/Peller type operators acting on vector-valued weighted Bergman spaces. We prove that a commuting n-tuple of such operators is jointly (completely) polynomially bounded if and only if it is similar to an n-tuple of contractions, if and only if each of the n operators is polynomially bounded.     

Intrinsic ordering,combinatorial numbers and reliability engineering

A new algorithm for evaluating the top event probability of large fault trees (FTs) is presented. This algorithm does not require any previous qualitative analysis of the FT. Indeed, its efficiency is independent of the FT logic, and it only depends on the number n of basic system components and on their failure probabilities. Our method provides exact lower and upper bounds on the top event probability by using new properties of the intrinsic order relation between binary strings. The intrinsic order enables one to select binary n  -tuples with large occurrence probabilities without necessity to evaluate them. This drastically reduces the complexity of the problem from exponential (2ⁿ$2^n$ binary n-tuples) to linear (n Boolean variables). Our algorithm is mainly based on a recursive formula for rapidly computing the sum of the occurrence probabilities of all binary n-tuples with weight m whose 1s are placed among the k right-most positions. This formula, as well as the balance between accuracy and computational cost, is closely related to the famous Pascal’s triangle.     

Models for n-tuples of noncommuting operators

This paper proves versions of the Rota model theorem, the de Branges-Rovnyak model theorem, and the coisometric extension theorem for n-tuples of not necessarily commuting operators. This generalizes the work of A. E. Frazho (J. Funct. Anal.48 (1982), 1–11) for pairs of operators. The methods involve applying the single operator results to matrices of operators.     

On the intersection of null spaces for matrix substitutions in a non-commutative rational formal power series

For a rational formal power series in N non-commuting indeterminates, with matrix coefficients, we establish the formula which relates the intersection of the null spaces of coefficients to the intersection of the null spaces of values of this series at N-tuples of $n\times n$ matrices, for n large enough. As an application, we formulate the criteria of observability, controllability, and minimality for a recognizable formal power series representation in terms of matrix substitutions. To cite this article: D. Alpay, D.S. Kalyuzhny??-Verbovetzki??, C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

Piecewise periodicity structure estimates in Shirshov’s height theorem

The Gelfand-Kirillov dimension of l-generated general matrices is equal to (l ? 1)n ² + 1. Due to the Amitzur-Levitsky theorem, the minimal degree of the identity of this algebra is 2n. That is why the essential height of A being an l-generated PI-algebra of degree n over every set of words is greater than (l ? 1)n ²/4 + 1. In this paper we prove that if A has a finite Gelfand-Kirillov dimension, then the number of lexicographically comparable subwords with the period (n ? 1) in each monoid of A is not greater than (l ? 2)(n ? 1). The case of subwords with the period 2 can be generalized to the proof of Shirshov’s height theorem.     

Congruence Criteria for Finite Subsets of Quaternionic Elliptic and Quaternionic Hyperbolic Spaces

We investigate congruence classes of m-tuples of points in the quaternionic elliptic space ?P ⁿ . We establish a canonical bijection between the set of congruence classes of m-tuples of points in ?P ⁿ and the set of equivalence classes of positive semidefinite Hermitian m×m matrices of rank at most n+1 with the 1's on the diagonal. We show that with each m-tuple of points in ?P ⁿ is associated a tuple of points on the real unit sphere S ². Then we get that the congruence class of an m-tuple of points in ?P ⁿ is determined by the congruence classes of all its triangles and by the direct congruence class of the associated tuple on the sphere S ² provided that no pair of points of the m-tuple has distance π/2. Finally we carry out the same kind of investigation for the quaternionic hyperbolic space ?H ⁿ . Most of the results are completely analogous, although there are also some interesting differences.     

Recent Developments In Harmonic Approximation,With Applications

A theorem of J.L. Walsh (1929) says that if E is a compact subset of Rⁿ with connected complement and if u is harmonic on a neighbourhood of E, then u can be uniformly approximated on E by functions harmonic on the whole of Rⁿ. In Part I of this article we survey some generalizations of Walsh’s theorem from the period 1980–94. In Part II we discuss applications of Walsh’s theorem and its generalizations to four diverse topics: universal harmonic functions, the Radon transform, the maximum principle, and the Dirichlet problem.     

Decompositions of complete graphs into regular bichromatic factors

The proof of the following theorem is given: A complete graph with n vertices can be decomposed into r regular bichromatic factors if and only if n is even and greater than 4 and there exists a natural number k with the properties that k ≤ r and 2^{k ? 1} < n ≤ 2^k.     

A combinatorial approach for Keller's conjecture

The statement, that in a tiling by translates of ann-dimensional cube there are two cubes having common (n-1)-dimensional faces, is known as Keller's conjecture. We shall prove that there is a counterexample for this conjecture if and only if the following graphs _n has a 2 ⁿ size clique. The 4 ⁿ vertices of _n aren-tuples of integers 0, 1, 2, and 3. A pair of thesen-tuples are adjacent if there is a position at which the difference of the corresponding components is 2 modulo 4 and if there is a further position at which the corresponding components are different. We will give the size of the maximal cliques of _n forn5.     

Lie properties of symmetric elements in group rings

Let ¹ be an involution of a group G extended linearly to the group algebra KG. We prove that if G contains no 2-elements and K is a field of characteristic $p\ne 2$, then the 1-symmetric elements of KG are Lie nilpotent (Lie n-Engel) if and only if KG is Lie nilpotent (Lie n-Engel).     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Universal functions for classes of Boolean polynomials

The following problem is considered: Find Boolean function f of n variables with the property that, given any polynomial p of degree at most s, there exists a set of n-tuples such that p is the only polynomial of degree at most s taking the same values as f at these n-tuples. It is shown that for any fixed s and sufficiently large n, such a function exists and can be chosen from among those with domains of cardinality that grow as O(n ^s ).     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

On some notions of spectra for quaternionic operators and for n-tuples of operators

The S-spectrum has been introduced for the definition of the S-functional calculus that includes both the quaternionic functional calculus and a calculus for n-tuples of nonnecessarily commuting operators. The notion of right spectrum for right linear quaternionic operators has been widely used in the literature, especially in the context of quaternionic quantum mechanics. Moreover, several results in linear algebra, like the spectral theorem for quaternionic matrices, involve the right spectrum. In this Note we prove that the two notions of S-spectrum and of right spectrum coincide.     

Embedding Tn-like continua in Euclidean space

Many authors have been concerned with embedding ∏-like continua in Rⁿ where ∏ is some collection of polyhedra or manifolds. A similar concern has been embedding ∏-like continua in Rⁿ up to shape. In this paper we prove two main theorems. Theorem: If n ? 2 and X is Tⁿ-like, then X embeds in R²ⁿ. This result was conjectured by McCord for the case H¹(X) finitely generated and proved by McCord for the case that H¹(X) = 0 using a theorem of Isbell. The second theorem is a shape embedding theorem. Theorem: If X is Tⁿ-like, then X embeds in Rⁿ⁺² up to shape. This theorem is proved by showing that an n-dimensional compact connected abelian topological group embeds in Rⁿ⁺². Any Tⁿ-like continuum is shape equivalent to a k-dimensional compact connected abelian topological group for some 0 ? k ? n.