Values of the Euler Function in Various Sequences

Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)^r = λ(n)^s, where r ≥ s ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.     

On a Conjecture of Kemnitz

A classic theorem of Erdis, Ginzburg and Ziv states that in a sequence of 2n-1 integers there is a subsequence of length n whose sum is divisble by n. This result has led to several extensions and generalizations. A multi-dimensional problem from this line of research is the following. Let Z_nZ_n stand for the additive group of integers modulo n. Let s(n, d) denote the smallest integer s such that in any sequence of s elements from Z_n^dZ_n^d (the direct sum of d copies of Z_nZ_n) there is a subsequence of length n whose sum is 0 in Z_n^dZ_n^d. Kemnitz conjectured that s(n, 2) = 4n - 3. In this note we prove that s(p,2) ￡ 4p - 2s(p,2) \le 4p - 2 holds for every prime p. This implies that the value of s(p, 2) is either 4p-3 or 4p-2. For an arbitrary positive integer n it follows that s(n, 2) ￡ (41/10)ns(n, 2) \le (41/10)n. The proof uses an algebraic approach.     

Admissibility and complete class results for the multinomial estimation problem with entropy and squared error loss

Let X ≡ (X₁, …, X_t) have a multinomial distribution based on N trials with unknown vector of cell probabilities p ≡ (p₁, …, p_t). This paper derives admissibility and complete class results for the problem of simultaneously estimating p under entropy loss (EL) and squared error loss (SEL). Let and f(x¦p) denote the (t − 1)-dimensional simplex, the support of X and the probability mass function of X, respectively. First it is shown that δ is Bayes w.r.t. EL for prior P if and only if δ is Bayes w.r.t. SEL for P. The admissible rules under EL are proved to be Bayes, a result known for the case of SEL. Let Q denote the class of subsets of of the form T = _j=1^kF_j where k ≥ 1 and each F_j is a facet of which satisfies: F a facet of such that F naF_jF ncT. The minimal complete class of rules w.r.t. EL when N ≥ t − 1 is characterized as the class of Bayes rules with respect to priors P which satisfy P( ⁰) = 1, ξ(x) ≡ ∫ f(x¦p) P(dp) > 0 for all x in {x : sup ^₀ f(x¦p) > 0} for some ⁰ in Q containing all the vertices of . As an application, the maximum likelihood estimator is proved to be admissible w.r.t. EL when the estimation problem has parameter space Θ = but it is shown to be inadmissible for the problem with parameter space Θ = ( minus its vertices). This is a severe form of “tyranny of boundary.” Finally it is shown that when N ≥ t − 1 any estimator δ which satisfies δ(x) > 0 x is admissible under EL if and only if it is admissible under SEL. Examples are given of nonpositive estimators which are admissible under SEL but not under EL and vice versa.     

Classes of orderings of measures and related correlation inequalities II. Multivariate reverse rule distributions

A function f(x) defined on = ₁ × ₂ × … × _n where each _i is totally ordered satisfying f(x y) f(x y) ≥ f(x) f(y), where the lattice operations and refer to the usual ordering on , is said to be multivariate totally positive of order 2 (MTP₂). A random vector Z = (Z₁, Z₂,…, Z_n) of n-real components is MTP₂ if its density is MTP₂. Classes of examples include independent random variables, absolute value multinormal whose covariance matrix Σ satisfies −DΣ⁻¹D with nonnegative off-diagonal elements for some diagonal matrix D, characteristic roots of random Wishart matrices, multivariate logistic, gamma and F distributions, and others. Composition and marginal operations preserve the MTP₂ properties. The MTP₂ property facilitate the characterization of bounds for confidence sets, the calculation of coverage probabilities, securing estimates of multivariate ranking, in establishing a hierarchy of correlation inequalities, and in studying monotone Markov processes. Extensions on the theory of MTP₂ kernels are presented and amplified by a wide variety of applications.     

Efficient p-adic Cell Decompositions for Univariate Polynomials

Cell decompositions are constructed for polynomials f(x)Z_p[x] of degree n, such that n<p, using O(n²) cells. When f is square-free this yields a polynomial-time algorithm for counting and approximating roots in Z_p. These results extend to give a polynomial-time algorithm in the bit model for fZ[x].     

Contributions to zero-sum problems

A prototype of zero-sum theorems, the well-known theorem of Erd?s, Ginzburg and Ziv says that for any positive integer n, any sequence a₁,a₂,…,a_2n-1 of 2n-1 integers has a subsequence of n elements whose sum is 0 modulo n. Appropriate generalizations of the question, especially that for (Z/pZ)^d, generated a lot of research and still have challenging open questions. Here we propose a new generalization of the Erd?s-Ginzburg-Ziv theorem and prove it in some basic cases.     

Precise asymptotics in some strong limit theorems for multidimensionally indexed random variables

Consider Z₊^d (d2)—the positive d-dimensional lattice points with partial ordering , let {X_k,kZ₊^d} be i.i.d. random variables with mean 0, and set S_n=∑_knX_k, nZ₊^d. We establish precise asymptotics for ∑_n|n|^r/p−2P(|S_n||n|^1/p), and for

Full-size image

, (0δ1) as 0, and for

Full-size image

as .     

Pairwise intersections and forbidden configurations

Let f_m(a,b,c,d) denote the maximum size of a family of subsets of an m-element set for which there is no pair of subsets with

By symmetry we can assume a≥d and b≥c. We show that f_m(a,b,c,d) is Θ(m^a+b−1) if either b>c or a,b≥1. We also show that f_m(0,b,b,0) is Θ(m^b) and f_m(a,0,0,d) is Θ(m^a). The asymptotic results are as m→∞ for fixed non-negative integers a,b,c,d. This can be viewed as a result concerning forbidden configurations and is further evidence for a conjecture of Anstee and Sali. Our key tool is a strong stability version of the Complete Intersection Theorem of Ahlswede and Khachatrian, which is of independent interest.     

Kolmogorov Width of Classes of Smooth Functions on the Sphere

Let ^d−1{(x₁,…,x_d) ^d:x²₁+···+x²_d=1} be the unit sphere of the d-dimensional Euclidean space ^d. For r>0, we denote by B^r_p (1p∞) the class of functions f on ^d−1 representable in the formwhere dσ(y) denotes the usual Lebesgue measure on ^d−1, and P^λ_k(t) is the ultraspherical polynomial.For 1p,q∞, the Kolmogorov N-width of B^r_p in L^q( ^d−1) is given bythe left-most infimum being taken over all N-dimensional subspaces X_N of L^q( ^d−1).The main result in this paper is that for r2(d−1)²,where A_NB_N means that there exists a positive constant C, independent of N, such that C⁻¹A_NB_NCA_N.This extends the well-known Kashin theorem on the asymptotic order of the Kolmogorov widths of the Sobolev class of the periodic functions.     

Propriétés statistiques des entiers friables

Let Ψ(x,y) (resp. Ψ_m(x,y)) denote the number of integers not exceeding x that are y-friable, i.e. have no prime factor exceeding y (resp. and are coprime to m). Evaluating the ratio Ψ_m(x/d,y)/Ψ(x,y) for 1≤slantd≤slantx, m≥slant 1, x≥slant y≥slant 2, turns out to be a crucial step for estimating arithmetic sums over friable integers. Here, it is crucial to obtain formulae with a very wide range of validity. In this paper, several uniform estimates are provided for the aforementioned ratio, which supersede all previously known results. Applications are given to averages of various arithmetic functions over friable integers which in turn improve corresponding results from the literature. The technique employed rests mainly on the saddle-point method, which is an efficient and specific tool for the required design.2000 Mathematics Subject Classification: Primary—11N25; Secondary—11K65, 11N37     

The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items

The First-Fit-Decreasing (FFD) algorithm is one of the most famous and most studied methods for an approximative solution of the bin-packing problem. The question on the parametric behavior of the FFD heuristic for small items was raised in D. S. Johnson's thesis (1973, MIT, Cambridge, MA) and in E. G. Coffman et al. (1987, SIAM J. Comput.7, 1–17): what is the asymptotic worst-case ratio for FFD when restricted to lists with item sizes in the interval (0, α] for α ≤ . Let R^∞_FFD(α) denote the asymptotic worst-case ratio for these lists. In his thesis, Johnson gave the values of R^∞_FFD(α) for and he conjectured that

Full-size image

for all integers m ≥ 4. J. Csirik (1993, J. Algorithms15, 1–28) proved that, for all integers m ≥ 5, this conjecture is true when m is even. When m is odd, he further showed where G_m ≡ 1 + (m² + m − 1)/(m(m + 1)(m + 2)) = F_m + 1/(m(m + 1)(m + 2)). These results leave open the values of R^∞_FFD(α) for 0 < α < 1/5 that are not the reciprocals of integers. In this paper we resolve the remaining open cases.     

Extremal Regular Graphs with Prescribed Odd Girth

The odd girth of a graph G gives the length of a shortest odd cycle in G. Let ƒ(k, g) denote the smallest n such that there exists a k-regular graph of order n and odd girth g. It is known that ƒ(k, g) ≥ kg/2 and that ƒ(k, g) = kg/2 if k is even. The exact values of ƒ(k, g) are also known if k = 3 or g = 5. Let x_e denote the smallest even integer no less than x, δ(g) = (−1)^{g − 1}/2, and s(k) = min {p + q | k = pq, where p and q are both positive integers}. It is proved that if k ≥ 5 and g ≥ 7 are both odd, then [formula] with the exception that ƒ(5, 7) = 20.     

Average Width and Optimal Interpolation of the Sobolev-Wiener Class Wpq(R) in the Metric Lq(R)

In this paper, we determine the exact value of average n − K width _n(W^r_pq(R), L_q(R)) of Sobolev-Wiener class W^r_pq(R) in the metric L_q(R) for 1 > q ≥ p > ∞ and get the value of _n(W^r_p(R), L_qp(R)) for the dual case. We also solve the optimal interpolation problems of W^r_pq(R) in the metric L_q(R) and W^r_p(R) in the metric L_qp(R) for 1 < q ≤ p < ∞.     

On Kemnitz’ conjecture concerning lattice-points in the plane

In 1961, Erdős, Ginzburg and Ziv proved a remarkable theorem stating that each set of 2n−1 integers contains a subset of size n, the sum of whose elements is divisible by n. We will prove a similar result for pairs of integers, i.e. planar lattice-points, usually referred to as Kemnitz’ conjecture. Dedicated to Richard Askey on the occasion of his 70th birthday. 2000 Mathematics Subject Classification Primary—11B50.     

Characterising the Accuracy of Multivariable Refinable Functions via the Symbol Function

Suppose that f(x) = (f ₁(x),...,f _r (x)) ^T , x∈R ^d is a vector-valued function satisfying the refinement equation f(x) = ∑_Λ c _κ f(2x−κ) with finite set Λ of Z ^d and some r×r matricex c _κ. The requirements for f to have accuracy p are given in terms of the symbol function m(ξ). Supported by NSFC     

Generalizations of Heilbronn’s triangle problem

For given integers d,j≥2 and any positive integers n, distributions of n points in the d-dimensional unit cube [0,1]^d are investigated, where the minimum volume of the convex hull determined by j of these n points is large. In particular, for fixed integers d,k≥2 the existence of a configuration of n points in [0,1]^d is shown, such that, simultaneously for j=2,…,k, the volume of the convex hull of any j points among these n points is Ω(1/n^{(j−1)/(1+|d−j+1|)}). Moreover, a deterministic algorithm is given achieving this lower bound, provided that d+1≤j≤k.     

Hardy spaces <Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript> for Schrödinger operators with compactly supported potentials

Let L=-Δ+V be a Schrödinger operator on ℝ^d, d≥3, where V is a non-negative compactly supported potential that belongs to L^p for some p>d/2. Let {K_t}_t>0 denote the semigroup of linear operators generated by -L. For a function f we define its H¹_L-norm by 0} |K_t f(x)|\|_{L^1(dx)}$" align="middle" border="0"> . It is proved that for a properly defined weight w a function f belongs to H¹_L if and only if wf∈H¹(ℝ^d), where H¹(ℝ^d) is the classical real Hardy space. Mathematics Subject Classification (2000) 42B30, 35J10, 42B25     

Inequalities for predictive ratios and posterior variances in natural exponential families

The predictive ratio is considered as a measure of spread for the predictive distribution. It is shown that, in the exponential families, ordering according to the predictive ratio is equivalent to ordering according to the posterior covariance matrix of the parameters. This result generalizes an inequality due to Chaloner and Duncan who consider the predictive ratio for a beta-binomial distribution and compare it with a predictive ratio for the binomial distribution with a degenerate prior. The predictive ratio at x₁ and x₂ is defined to be p_g(x₁)p_g(x₂)/[p_g( )]² = h_g(x₁, x₂), where p_g(x₁) = ∫ ƒ(x₁θ) g(θ) dθ is the predictive distribution of x₁ with respect to the prior g. We prove that h_g(x₁, x₂) ≥ h_g^*(x₁, x₂) for all x₁ and x₂ if ƒ(xθ) is in the natural exponential family and Cov_gx(θ) ≥ Cov_g^*x(θ) in the Loewner sense, for all x on a straight line from x₁ to x₂. We then restrict the class of prior distributions to the conjugate class and ask whether the posterior covariance inequality obtains if g and g^* differ in that the “sample size”     

Energy of Flows on Percolation Clusters

It is well known for which gauge functions H there exists a flow in Z ^d with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows. Instead of Z ^d we let our (random) graph cal C cal (Z ^d,p) be the graph obtained from Z ^d by removing edges with probability 1–p independently on all edges. Grimmett, Kesten, and Zhang (1993) showed that for d3,p>p _c(Z ^d), simple random walk on cal C cal (Z ^d,p) is a.s. transient. Their result is equivalent to the existence of a nonzero flow f on the infinite cluster such that the x ² energy _e f(e)² is finite. Levin and Peres (1998) sharpened this result, and showed that if d3 and p>p _c(Z ^d), then cal C cal (Z ^d,p) supports a nonzero flow f such that the x ^q energy is finite for all q>d/(d–1). However, for general gauge functions, there is a gap between the existence of flows with finite energy which results from the work of Levin and Peres and the known results on flows for Z ^d. In this paper we close the gap by showing that if d3 and Z ^d supports a flow of finite H energy then the infinite percolation cluster on Z ^d also support flows of finite H energy. This disproves a conjecture of Levin and Peres.     

RELATIVE WIDTH OF SMOOTH CLASSES OF MULTIVARIATE PERIODIC FUNCTIONS WITH RESTRICTIONS ON ITERATED LAPLACE DERIVATIVES IN THE L2-METRIC

For two subsets W and V of a Banach space X, let Kn(W, V, X) denote the relative Kolmogorov n-width of W relative to V defined by Kn (W, V, X) := inf sup Ln f∈W g∈V∩Ln inf ‖f-g‖x,where the infimum is taken over all n-dimensional linear subspaces Ln of X. Let W2(△r) denote the class of 2w-periodic functions f with d-variables satisfying ∫[-π,π]d |△rf(x)|2dx ≤ 1,while △r is the r-iterate of Laplace operator △. This article discusses the relative Kolmogorov n-width of W2(△r) relative to W2(△r) in Lq([-r, πr]d) (1 ≤ q ≤∞), and obtain its weak asymptotic result.