Rearrangements of (0–1) matrices

Let ℬ(m) be the set of all then-square (0–1) matrices containingm ones andn ²−m zeros, 0<m<n ². The problem of finding the maximum ofs(A ²) over this set, wheres(A ²) is the sum of the entries ofA ²,A ∈ ℬ (m) is considered. This problem is solved in the particular casesm=n ² −k ² andm=k ²,k ²>(n ²/2). This paper forms part of a thesis in partial fulfillment of the requirements for the degree of Doctor of Science at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Dr. D. London for their help in the preparation of this paper.     

Restricted sumsets and a conjecture of Lev

LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev. This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars (No. 10425103) and the Key Program of NSF (No. 10331020) in China.     

An Extremal Problem on Degree Sequences of Graphs

 Let G=(I _n ,E) be the graph of the n-dimensional cube. Namely, I _n ={0,1} ⁿ and [x,y]∈E whenever ||x−y||₁=1. For A⊆I _n and x∈A define h _A (x) =#{y∈I _n A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I _n of size 2 ⁿ⁻¹ we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices. Received: January 7, 2000 RID="*" ID="*" Supported in part by BSF and by the Israeli academy of sciences     

The Gleason’s problem for some polyharmonic and hyperbolic harmonic function spaces

Let Ω ⊆ ℝⁿ be a bounded convex domain with C ² boundary. For 0 < p, q ⩽ ∞ and a normal weight φ, the mixed norm space H _k ^p,q,φ (Ω) consists of all polyharmonic functions f of order k for which the mixed norm ∥ · ∥_p,q,φ < ∞. In this paper, we prove that the Gleason’s problem (Ω, a, H _k ^p,q,φ ) is always solvable for any reference point a ∈ Ω. Also, the Gleason’s problem for the polyharmonic φ-Bloch (little φ-Bloch) space is solvable. The parallel results for the hyperbolic harmonic mixed norm space are obtained.     

Algebras whose equivalence relations are congruences

It is proved that all the equivalence relations of a universal algebra A are its congruences if and only if either |A| ≤ 2 or every operation f of the signature is a constant (i.e., f(a ₁ , . . . , a _n ) = c for some c ∈ A and all the a ₁ , . . . , a _n ∈ A) or a projection (i.e., f(a ₁ , . . . , a _n ) = a _i for some i and all the a ₁ , . . . , a _n ∈ A). All the equivalence relations of a groupoid G are its right congruences if and only if either |G| ≤ 2 or every element a ∈ G is a right unit or a generalized right zero (i.e., x _a  = y _a for all x, y ∈ G). All the equivalence relations of a semigroup S are right congruences if and only if either |S| ≤ 2 or S can be represented as S = A∪B, where A is an inflation of a right zero semigroup, and B is the empty set or a left zero semigroup, and ab = a, ba = a ² for a ∈ A, b ∈ B. If G is a groupoid of 4 or more elements and all the equivalence relations of it are right or left congruences, then either all the equivalence relations of the groupoid G are left congruences, or all of them are right congruences. A similar assertion for semigroups is valid without the restriction on the number of elements.     

Tracking and invariance problems for some classes of discrete delay systems

Consider the system with perturbation g _k ∈ ℝ ⁿ and output z _k = Cx _k . Here, A _k ,A _k ^(s) ∈ ℝ ^{n × n} , B _k ⁽¹⁾ ∈ ℝ ^{n × p} , B _k ⁽²⁾ ∈ ℝ ^{n × m} , C ∈ ℝ ^{p × n} . We construct a special Lyapunov-Krasovskii functional in order to synthesize controls u _k ⁽¹⁾ and u _k ⁽²⁾ for which the following properties are satisfied:

{0, 1/2}-Chvátal-Gomory cuts

Given the integer polyhedronP _t := conv{x ∈ℤ ⁿ :Ax⩽b}, whereA ∈ℤ ^{m × n} andb ∈ℤ ^m , aChvátal-Gomory (CG)cut is a valid inequality forP ₁ of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ ₊ ^m such that λτA∈ℤ ⁿ . In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2} ^m . We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of strong inequalities forP ₁. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.     

On invariant additive subgroups

Suppose thatR is a prime ring with the centerZ and the extended centroidC. An additive subgroupA ofR is said to be invariant under special automorphisms if (1+t)A(1+t)⁻¹ ⊆A for allt ∈R such thatt ²=0. Assume thatR possesses nontrivial idempotents. We prove: (1) If chR ≠ 2 or ifRC ≠C ₂, then any noncentral additive subgroup ofR invariant under special automorphisms contains a noncentral Lie ideal. (2) If chR=2,RC=C ₂ andC ≠ {0, 1}, then the following two conditions are equivalent: (i) any noncentral additive subgroup invariant under special automorphisms contains a noncentral Lie ideal; (ii) there isα ∈Z / {0} such thatα ² Z ⊆ {β ²:β ∈Z}.     

Additive Latin transversals and group rings

LetA={a ₁, …,a _k} and {b ₁, …,b _k} be two subsets of an abelian groupG, k≤|G|. Snevily conjectured that, when |G| is odd, there is a numbering of the elements ofB such thata _i+b _i,1≤i≤k are pairwise distinct. By using a polynomial method, Alon affirmed this conjecture for |G| prime, even whenA is a sequence ofk<|G| elements. With a new application of the polynomial method, Dasgupta, Károlyi, Serra and Szegedy extended Alon’s result to the groupsZ _p ^r andZ _p ^rin the casek<p and verified Snevily’s conjecture for every cyclic group. In this paper, by employing group rings as a tool, we prove that Alon’s result is true for any finite abelianp-group withk<√2p, and verify Snevily’s conjecture for every abelian group of odd order in the casek<√p, wherep is the smallest prime divisor of |G|. This work has been supported partly by NSFC grant number 19971058 and 10271080.     

Potenzieren und Wurzelziehen in rationalen Quaternionenalgebren

LetF be a field not of characteristic 2 andQ =F +F i +F j +F k the quaternion algebra overF whereij = -ji =k andi ² = α andj ² = β with 0 ≠ α, β ∈F fixed. (IfF = ℝ and α = β = - 1 thenQ is the division algebra of the Hamilton quaternions.) IfF = ℚ and Q is a division algebra then by embedding certain quadratic number fields inQ we derive an efficient formula to compute the powers of any quaternion. This formula is even true in general and reads as follows. If a, a₁, a₂, a₃ ∈F andn ∈ ℕ then where ω ig a square root of αa₁ ² + βa ₂ ² - αβa ₃ ² in or overF and andA ₀ =na ^n-1. With the help of this formula and related ones we are able to solve the equationX ⁿ =q for arbitrary quaternionsq and positive integers n in case ofF = ℝ and hence in case ofF ⊂ ℝ as well. IfF = ℝ then the total number of all solutions equals 0, 1, 2, 4,n or ∞. (4 is possible even whenn < 4.) In case ofF = ℚ, which we are primarily interested in, there are always either at most six or infinitely many solutions. Further, for everyq ≠ 0 there is at most one solution provided thatn is odd and not divisible by 3. The questions when there are infinitely many solutions and when there are none can always be decided by checking simple conditions on the radicandq ifF = ℝ. ForF = ℚ the two questions are comprehensively investigatet in a natural connection with ternary and quaternary quadratic rational forms. Finally, by applying some of our theorems on powers and roots of quate-rions we also obtain several nice results in matrix theory. For example, for every k ∈ ℤ the mappingA ↦A ^k on the group of all nonsingular 2-by-2 matrices over ℚ is injective if and only ifk is odd and not divisible by 3.

     

The postage stamp problem and arithmetic in base <Emphasis Type="Italic">r</Emphasis>

Let h, k be fixed positive integers, and let A be any set of positive integers. Let hA ≔ {a ₁ + a ₂ + ... + a _r : a _i ∈ A, r ⩽ h} denote the set of all integers representable as a sum of no more than h elements of A, and let n(h, A) denote the largest integer n such that {1, 2,...,n} ⊆ hA. Let n(h, k) := : n(h, A), where the maximum is taken over all sets A with k elements. We determine n(h, A) when the elements of A are in geometric progression. In particular, this results in the evaluation of n(h, 2) and yields surprisingly sharp lower bounds for n(h, k), particularly for k = 3.     

Factorization for non-nevanlinna classes of analytic functions

A generalization of the Blaschke product is constructed. This product enables one to factor out the zeros of the members of certain non-Nevanlinna classes of functions analytic in the unit disc, so that the remaining (non-vanishing) functions still belong to the same class. This is done for the classesA ⁻ⁿ (0<n<∞) andB ⁻ⁿ (0<n<2) defined as follows:f ∈A ⁻ⁿ iff |f(z)|≦C _f (1−|z|)⁻ⁿ ,f ∈B ⁻ⁿ iff |f(z)|≦exp {C _f (1−|z|)⁻ⁿ }, whereC _f depends onf.     

Transversals of additive Latin squares

LetA={a ₁, …,a _k} andB={b ₁, …,b _k} be two subsets of an Abelian groupG, k≤|G|. Snevily conjectured that, whenG is of odd order, there is a permutationπ ∈S _ksuch that the sums α _i +b _i , 1≤i≤k, are pairwise different. Alon showed that the conjecture is true for groups of prime order, even whenA is a sequence ofk<|G| elements, i.e., by allowing repeated elements inA. In this last sense the result does not hold for other Abelian groups. With a new kind of application of the polynomial method in various finite and infinite fields we extend Alon’s result to the groups (ℤ _p ) ^a and in the casek<p, and verify Snevily’s conjecture for every cyclic group of odd order. Supported by Hungarian research grants OTKA F030822 and T029759. Supported by the Catalan Research Council under grant 1998SGR00119. Partially supported by the Hungarian Research Foundation (OTKA), grant no. T029132.     

A nilpotent Roth theorem

Let T and S be invertible measure preserving transformations of a probability measure space (X, ℬ, μ). We prove that if the group generated by T and S is nilpotent, then exists in L ²-norm for any u, v∈L ^∞(X, ℬ, μ). We also show that for A∈ℬ with μ(A)>0 one has . By the way of contrast, we bring examples showing that if measure preserving transformations T, S generate a solvable group, then (i) the above limits do not have to exist; (ii) the double recurrence property fails, that is, for some A∈ℬ, μ(A)>0, one may have μ(A∩T _-n A∩S ^{- n} A)=0 for all n∈ℕ. Finally, we show that when T and S generate a nilpotent group of class ≤c, in L ²(X) for all u, v∈L ^∞(X) if and only if T×S is ergodic on X×X and the group generated by T ^-1 S, T ^-2 S ²,..., T ^-c S ^c acts ergodically on X. Oblatum 19-V-2000 & 5-VII-2001?Published online: 12 October 2001     

Embedding ofl ∞ k in finite dimensional Banach spaces

Letx ₁,x ₂, ...,x _n ben unit vectors in a normed spaceX and defineM _n =Ave{‖Σ _i=1 ⁿ ε₁ x _i ‖:ε₁=±1}. We prove that there exists a setA⊂{1, ...,n} of cardinality such that {x _i } _i∈A is 16M _n -isomorphic to the natural basis ofl _∞ ^k . This result implies a significant improvement of the known results concerning embedding ofl _∞ ^k in finite dimensional Banach spaces. We also prove that for every ∈>0 there exists a constantC(∈) such that every normed spaceX _n of dimensionn either contains a (1+∈)-isomorphic copy ofl ₂ ^m for somem satisfying ln lnm≧1/2 ln lnn or contains a (1+∈)-isomorphic copy ofl _∞ ^k for somek satisfying ln lnk>1/2 ln lnn−C(∈). These results follow from some combinatorial properties of vectors with ±1 entries. The contribution of the first author to this paper forms part of his Ph.D. Thesis written under the supervision of Prof. M. A. Perles from the Hebrew University.     

The additive subgroup generated by a polynomial

SupposeR is a prime ring with the centerZ and the extended centroidC. Letp(x ₁, …,x _n) be a polynomial overC in noncommuting variablesx ₁, …,x _n. LetI be a nonzero ideal ofR andA be the additive subgroup ofRC generated by {p(a ₁, …,a _n):a ₁, …,a _n ∈I}. Then eitherp(x ₁, …,x _n) is central valued orA contains a noncentral Lie ideal ofR except in the only one case whereR is the ring of all 2 × 2 matrices over GF(2), the integers mod 2.     

On the commutant of certain multiplication operators on spaces of analytic functions

Let ℬ be a Banach space of analytic functions defined on the open unit disk. We characterize the commutant ofM _Z ² (the operator of multiplication by the square of independent variable defined on ℬ) and show that for an operatorS in the commutantM _Z ² ifSM _Z ^2k+1−M _Z ^2k+1 S is compact for some nonnegative integerk, thenS=M _ϕ whereϕ is a multiplier of ℬ. Letn be a positive integer andS be an operator in the commutant ofM _Z ⁿ defined on a functional Hilbert spaces of analytic functions. We show that under certain conditionsS has the formM _ϕ. Research supported by the Shiraz University Grant 78-SC-1188-657.     

Two point problems and analyticity of solutions of abstract parabolic equations

Fort ∈ [a, b], letA(t) be the unbounded operator inH ^0,p (G) associated with an elliptic-boundary value problem that satisfies Agmon’s conditions on the rays λ=±iτ, τ ≥0. Existence and uniqueness results are obtained for weak and strict solutions of two-point problems of the type (du/dt)−A(t) u(t) =f(t),E ₁(α)u (α)=u _α,E ₂ (β)u (β)=u _β. Here [α, β) χ- [a, b],E ₁ (α) andE ₂ (β) are spectral projections associated withA(α) andA(β) respectively, andA(α)E ₁ (α) and =A (β)E ₂ (β) are infinitesimal generators of analytic semigroups. WhenA(t) andf(t) are analytic in a convex, complex neighborhoodO of [a, b] we show that for someθ _i ,i=1,2, any solution ofdu/dt =A(t)u (t)=f(t) in [a, b] is analytic and satisfies the above equation in the setO∩{t; t ≠ a, t ≠ b, | arg (t −a) | <θ ₁, | arg (b −t) |θ ₂}. Research partially supported by N. N. F. grant at Brandeis University.