A proof of snevily’s conjecture

We prove Snevily’s conjecture, which states that for any positive integer k and any two k-element subsets {a ₁, …, a _k } and {b ₁, …, b _k } of a finite abelian group of odd order there exists a permutation π ∈ S _k such that all sums a _i + b _π(i) (i ∈ [1, k]) are pairwise distinct.     

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.     

A simple method for smoothing functions and compressing Hermite data

Let =(a=x₀<x₁<<x_n=b) be a partition of an interval [a,b] of R, and let f be a piecewise function of class C^k on [a,b] except at knots x_i where it is only of class , k_ik. We study in this paper a novel method which smooth the function f at x_i, 0in. We first define a new basis of the space of polynomials of degree 2k+1, and we describe algorithms for smoothing the function f. Then, as an application, we give a recursive computation of classical Hermite spline interpolants, and we present a method which allows us to compress Hermite data. The most part of these results are illustrated by some numerical examples. AMS subject classification 41A05, 41A15, 65D05, 65D07, 65D10     

Additive latin transversals

We prove that for every odd primep, everyk≤p and every two subsets A={a ₁, …,a _k } andB={b ₁, …,b _k } of cardinalityk each ofZ _p , there is a permutationπ ∈S _k such that the sumsa _i +b _π(i) (inZ _p ) are pairwise distinct. This partially settles a question of Snevily. The proof is algebraic, and implies several related results as well. Research supported in part by a State of New Jersey grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Convergence properties of sequences of functions with application to restricted derivative approximation

Convergence properties of sequences of continuous functions, with kth order divided differences bounded from above or below, are studied. It is found that for such sequences, convergence in a “monotone norm” (e.g., L_p) on [a, b] to a continuous function implies uniform convergence of the sequence and its derivatives up to order k − 1 (whenever they exist), in any closed subinterval of [a, b]. Uniform convergence in the closed interval [a, b] follows from the boundedness from below and above of the kth order divided differences. These results are applied to the estimation of the degree of approximation in Monotone and Restricted Derivative approximation, via bounds for the same problems with only one restricted derivative.     

On Extending Peano Derivatives

Let E be a closed set with inf E = a and sup E = b, and k be a positive integer. Let f : E Rbe such that the k-th Peano derivative of f relative to E, f _(k) (x, E), exists. It is proved under certain condition on the function f, that an extension F : [a, b] Rof f exists such that the ordinary derivative of F of order k, F ^<k> (x) exists on [a, b] and is continuous on [a, b], and f _<> (x, E) = F ^<i> (x) on E, for i = 1, 2, &, k.     

Oscillatory solutions of nonhomogeneous linear differential equations

The complex oscillation of nonhomogeneous linear differential equations with transcendental coefficients is discussed. Results concerning the equation f ^(k)+a _k−1 f ^(k−1)+...+a ₀ f=F where a ₀,...,a _k−i and Fare entire functions, possessing an oscillatory solution subspace in which all solutions (with at most one exception) have infinite exponent of convergence of zeros are obtained. All solutions of the equation are also characterized when the coefficients a ₀,a ₁,...,a _k−1 are polynomials and F=h exp (p ₀), where p ₀ is a polynomial and h is an entire function. Author supported by Max-Planck-Gesellschaft and by NSFC.     

Characterizing Profiles ofk-Families in Additive Macaulay Posets

A subset of a poset is ak-familyif there is no chain consisting ofk+1 of its elements. A subset of a ranked poset consisting ofp_i elements of ranki,i=0, 1, ..., Ris said to haveprofilep₀,p₁, …, p_R. A characterization is given for profiles ofk-families in additive Macaulay posets.     

Some remarks on hilbert functions of veronese algebras

We study the Hilbert polynomials of finitely generated graded algebras R, with generators not all of degree one (i.e. non-standard). Given an expression P(R,t)=a(t)/(1-t^l ) ⁿ for the Poincare series of R as a rational function, we study for 0 ≤ i ≤ l the graded subspaces ? _kR_kl+i (which we denote R[l;i]) of R, in particular their Poincaré series and Hilbert functions. We prove, for example, that if R is Cohen-Macaulay then the Hilbert polynomials of all non-zeroR[l;i] share a common degree. Furthermore, if R is also a domain then these Hilbert polynomials have the same leading coefficient.     

A remark on the intersection arrays of distance regular graphs and the distance regular graphs of diameter d = 3i − 1 with b i = 1 and k > 2

Let be a distance regular graph with intersection array b ₀, b ₁,..., b _d–1; c ₁,..., c _d. It is shown that in some cases (c _i–1, a _i–1, b _i–1) = (c ₁, a ₁, b ₁)and (c _2i–1, a _2i–1, b _2i–1) imply k 2b _i + 1. As a corollary all distance regular graphs of diameter d = 3i – 1 with b _i = 1 and k > 2 are determined.     

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.     

Extremal values of continuants and transcendence of certain continued fractions

We prove a criterion for the transcendence of continued fractions whose partial quotients are contained in a finite set {b₁,…,b_r} of positive integers such that the density of occurrences of b_i in the sequence of partial quotients exists for 1ir. As an application we study continued fractions [0,a₁,a₂,a₃,…] with a_n=1+([nθ]modd) where θ is irrational and d2 is a positive integer.     

Convexity preserving and predicting by Bernstein polynomials

It is known that the Bernstein polynomials of a function f defined on [0, 1 ] preserve its convexity properties, i.e., if f⁽ⁿ⁾ 0 then for m n, (B_mf)⁽ⁿ⁾ 0. Moreover, if f is n-convex then (B_mf)⁽ⁿ⁾ 0. While the converse is not true, we show that if f is bounded on (a, b) and if for every subinterval [α, β] (a, b) the nth derivative of the mth Bernstein polynomial of f on [α, β] is nonnegative then f is n-convex.     

Entropy splitting for antiblocking corners and perfect graphs

We characterize pairs of convex setsA, B in thek-dimensional space with the property that every probability distribution (p ₁,...,p _k ) has a repsesentationp _i =a _l .b _i , aA, bB.Minimal pairs with this property are antiblocking pairs of convex corners. This result is closely related to a new entropy concept. The main application is an information theoretic characterization of perfect graphs.Research was partially sponsored by the Hungarian National Foundation, Scientific Research Grants No 1806 and 1812.     

Uniformly More Powerful, Two-Sided Tests for Hypotheses about Linear Inequalities

Let Xhave a multivariate, p-dimensional normal distribution (p 2) with unknown mean and known, nonsingular covariance . Consider testing H ₀ : b _i 0, for some i = 1,..., k, and b _i 0, for some i = 1,..., k, versus H ₁ : b _i < 0, for all i = 1,..., k, or b _i < 0, for all i = 1,..., k, where b ₁,..., b _k , k 2, are known vectors that define the hypotheses and suppose that for each i = 1,..., k there is an j {1,..., k} (j will depend on i) such that b _i b _j 0. For any 0 < < 1/2. We construct a test that has the same size as the likelihood ratio test (LRT) and is uniformly more powerful than the LRT. The proposed test is an intersection-union test. We apply the result to compare linear regression functions.     

On computing the dispersion function

A two-dimensional analogue of the well-known bisection method for root finding is presented in order to solve the following problem, related to the dispersion function of a set of random variables: given distribution functionsF ₁,...,F _n and a probabilityp, find an interval [a,b] of minimum width such thatF _i(b)–F _i(a ^–)p, fori=1,...,n.The author wishes to thank Dr. I. D. Coope, for helpful advice offered during the preparation of this paper, and the referee, whose comments contributed to a clearer presentation.     

An optimal version of an inequality involving the third symmetric means

Let (GA) _n ^[k](a), A _n (a), G _n (a) be the third symmetric mean of k degree, the arithmetic and geometric means of a ₁, …, a _n (a _i > 0, i = 1, …, n), respectively. By means of descending dimension method, we prove that the maximum of p is k−1/n−1 and the minimum of q is n/n−1(k−1/k) ^k/n so that the inequalities {fx505-1} hold.     

Almost Schreier monoids

In an earlier paper, we introduced and studied the class of commutative integral domains D having the following property: if a, b₁, b₂ ? D{a, b_1, b_2 \in D} and a|b ₁ b ₂, there exist an integer k ≥ 1 and a₁, a₂ ? D{a_1, a_2 \in D} such that a ^k = a ₁ a ₂ and a_i|b_i^k , i = 1, 2{a_i|b{_i}^k , i = 1, 2} . In this paper, we show that many of our earlier results are purely multiplicative in the sense they can be extended to the setting of commutative cancellative monoids.     

Graph decompositions without isolated vertices III

Let G be a graph of order n, and n = Σ^k_i=1 a_i be a partition of n with a_i ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v₁,…, v_k of G, the vertex set V(G) can be decomposed into k disjoint subsets A₁,…, A_k so that |A_i| = a_i,v_iisA_i is an element of A_i and “the subgraph induced by A_i contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.     

Characterization of generalized convex functions by their best approximation in sign-monotone norms

Let {u₀, u₁,… u_{n − 1}} and {u₀, u₁,…, u_n} be Tchebycheff-systems of continuous functions on [a, b] and let f ε C[a, b] be generalized convex with respect to {u₀, u₁,…, u_{n − 1}}. In a series of papers ([1], [2], [3]) D. Amir and Z. Ziegler discuss some properties of elements of best approximation to f from the linear spans of {u₀, u₁,…, u_{n − 1}} and {u₀, u₁,…, u_n} in the L_p-norms, 1 p ∞, and show (under different conditions for different values of p) that these properties, when valid for all subintervals of [a, b], can characterize generalized convex functions. Their methods of proof rely on characterizations of elements of best approximation in the L_p-norms, specific for each value of p. This work extends the above results to approximation in a wider class of norms, called “sign-monotone,” [6], which can be defined by the property: ¦ f(x)¦ ¦ g(x)¦,f(x)g(x) 0, a x b, imply f g . For sign-monotone norms in general, there is neither uniqueness of an element of best approximation, nor theorems characterizing it. Nevertheless, it is possible to derive many common properties of best approximants to generalized convex functions in these norms, by means of the necessary condition proved in [6]. For {u₀, u₁,…, u_n} an Extended-Complete Tchebycheff-system and f ε C⁽ⁿ⁾[a, b] it is shown that the validity of any of these properties on all subintervals of [a, b], implies that f is generalized convex. In the special case of f monotone with respect to a positive function u₀(x), a converse theorem is proved under less restrictive assumptions.