A lower bound for the r -order of a matrix modulo N

For a positive integer N, we define the N-rank of a non singular integer d × d matrix A to be the maximum integer r such that there exists a minor of order r whose determinant is not divisible by N. Given a positive integer r, we study the growth of the minimum integer k, such that A ^k − I has N-rank at most r, as a function of N. We show that this integer k goes to infinity faster than log N if and only if for every eigenvalue λ which is not a root of unity, the sum of the dimensions of the eigenspaces relative to eigenvalues which are multiplicatively dependent with λ and are not roots of unity, plus the dimensions of the eigenspaces relative to eigenvalues which are roots of unity, does not exceed d − r − 1. This result will be applied to recover a recent theorem of Luca and Shparlinski [6] which states that the group of rational points of an ordinary elliptic curve E over a finite field with q ⁿ elements is almost cyclic, in a sense to be defined, when n goes to infinity. We will also extend this result to the product of two elliptic curves over a finite field and show that the orders of the groups of \Bbb F_qⁿ-{\Bbb F}_{q^n}- rational points of two non isogenous elliptic curves are almost coprime when n approaches infinity.     

Semiclassical <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> Estimates of Quasimodes on Curved Hypersurfaces

Let M be a compact manifold of dimension n, P=P(h) a semiclassical pseudodifferential operator on M, and u=u(h) an L ² normalized family of functions such that P(h)u(h) is O(h) in L ²(M) as h↓0. Let H⊂M be a compact submanifold of M. In a previous article, the second-named author proved estimates on the L ^p norms, p≥2, of u restricted to H, under the assumption that the u are semiclassically localized and under some natural structural assumptions about the principal symbol of P. These estimates are of the form Ch ^−δ(n,k,p) where k=dim H (except for a logarithmic divergence in the case k=n−2, p=2). When H is a hypersurface, i.e., k=n−1, we have δ(n,n−1, 2)=1/4, which is sharp when M is the round n-sphere and H is an equator.     

On the directions problem in <Emphasis Type="Italic">AG</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)

We prove that if q = p ^h , p a prime, do not exist sets U í AG(n,q){U {\subseteq} AG(n,q)}, with |U| = q ^k and 1 < k < n, determining N directions where

Rate of convergence to stationarity of the system <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">N</Emphasis>/<Emphasis Type="Italic">N</Emphasis>+<Emphasis Type="Italic">R</Emphasis>

We consider the M/M/N/N+R service system, characterized by N servers, R waiting positions, Poisson arrivals and exponential service times. We discuss representations and bounds for the rate of convergence to stationarity of the number of customers in the system, and study its behaviour as a function of R, N and the arrival rate λ, allowing λ to be a function of N.     

Distributions of Points in <Emphasis Type="Italic">d</Emphasis> Dimensions and Large <Emphasis Type="Italic">k</Emphasis>-Point Simplices

We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1] ^d , such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ _k,d (n), the supremum of this minimum volume over all distributions of n points in [0,1] ^d , we show that c _k,d ⋅(log n)^1/(d−k+1)/n ^k/(d−k+1)≤Δ _k,d (n)≤c _k,d ′/n ^k/d for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ _k,d (n)≤c _k,d ″/n ^{k/d+(k−1)/(2d(d−1))}, where c _k,d ,c _k,d ′,c _k,d ″>0 are constants. A preliminary version of this paper appeared in COCOON ’05.     

Best approximation by ridge functions in <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-spaces

We study the approximation of the classes of functions by the manifold R _n formed by all possible linear combinations of n ridge functions of the form r(a · x)): It is proved that, for any 1 ≤ q ≤ p ≤ ∞, the deviation of the Sobolev class W ^r _p from the set R _n of ridge functions in the space L _q (B ^d ) satisfies the sharp order n ^-r/(d-1).     

Maximal regular subsemibands of finite order-preserving transformation semigroups <Emphasis Type="Italic">K</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">r</Emphasis>)

Let O _n be the order-preserving transformation semigroup on X _n . For an arbitrary integer r such that 1≤r≤n−2, we completely describe the maximal regular subsemibands of the semigroup K(n,r)={α∈O _n :|im(α)|≤r}. We also formulate the cardinal number of such subsemigroups.     

On the family of diophantine triples {<Emphasis Type="Italic">k</Emphasis> + 1, 4<Emphasis Type="Italic">k</Emphasis>, 9<Emphasis Type="Italic">k</Emphasis> + 3}

We prove that if k is a positive integer and d is a positive integer such that the product of any two distinct elements of the set {k + 1, 4k, 9k + 3, d} increased by 1 is a perfect square, then d = 144k ³ + 192k ² + 76k + 8.      

Goal-minimally <Emphasis Type="Italic">k</Emphasis>-elongated graphs

Let k be an integer. A 2-edge connected graph G is said to be goal-minimally k-elongated (k-GME) if for every edge uv ∈ E(G) the inequality d _G−uv (x, y) > k holds if and only if {u, v} = {x, y}. In particular, if the integer k is equal to the diameter of graph G, we get the goal-minimally k-diametric (k-GMD) graphs. In this paper we construct some infinite families of GME graphs and explore k-GME and k-GMD properties of cages. This research was supported by the Slovak Scientific Grant Agency VEGA No. 1/0406/09.     

On proper secrets, (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-bases and linear codes

This paper contains three parts where each part triggered and motivated the subsequent one. In the first part (Proper Secrets) we study the Shamir’s “k-out-of-n” threshold secret sharing scheme. In that scheme, the dealer generates a random polynomial of degree k−1 whose free coefficient is the secret and the private shares are point values of that polynomial. We show that the secret may, equivalently, be chosen as any other point value of the polynomial (including the point at infinity), but, on the other hand, setting the secret to be any other linear combination of the polynomial coefficients may result in an imperfect scheme. In the second part ((t, k)-bases) we define, for every pair of integers t and k such that 1 ≤ t ≤ k−1, the concepts of (t, k)-spanning sets, (t, k)-independent sets and (t, k)-bases as generalizations of the usual concepts of spanning sets, independent sets and bases in a finite-dimensional vector space. We study the relations between those notions and derive upper and lower bounds for the size of such sets. In the third part (Linear Codes) we show the relations between those notions and linear codes. Our main notion of a (t, k)-base bridges between two well-known structures: (1, k)-bases are just projective geometries, while (k−1, k)-bases correspond to maximal MDS-codes. We show how the properties of (t, k)-independence and (t, k)-spanning relate to the notions of minimum distance and covering radius of linear codes and how our results regarding the size of such sets relate to known bounds in coding theory. We conclude by comparing between the notions that we introduce here and some well known objects from projective geometry.      

Upper bounds for prime <Emphasis Type="Italic">k</Emphasis>-tuples of size log <Emphasis Type="Italic">N</Emphasis> and oscillations

We prove the estimate for the number E_k(N) of k-tuples (n + a₁,..., n + a_k) of primes not exceeding N, for k of size c₁ log N and N sufficiently large. A bound of this strength was previously known in the special case < only, (Vaughan, 1973). For general a_i this is an improvement upon the work of Hofmann and Wolke (1996). The number of prime tuples of this size has considerable oscillations, when varying the prime pattern. Received: 20 December 2002     

Facets of the <Emphasis Type="Italic">r</Emphasis>-Stable (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-Hypersimplex

Let k, n, and r be positive integers with k < n and \({r \leq \lfloor \frac{n}{k} \rfloor}\). We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every \({r < \lfloor \frac{n}{k} \rfloor}\). We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart \({\delta}\)-vectors.     

Optimal (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) visual cryptographic schemes for general <Emphasis Type="Italic">k</Emphasis>

In (k, n) visual cryptographic schemes (VCS), a secret image is encrypted into n pages of cipher text, each printed on a transparency sheet, which are distributed among n participants. The image can be visually decoded if any k(≥2) of these sheets are stacked on top of one another, while this is not possible by stacking any k − 1 or fewer sheets. We employ a Kronecker algebra to obtain necessary and sufficient conditions for the existence of a (k, n) VCS with a prior specification of relative contrasts that quantify the clarity of the recovered image. The connection of these conditions with an L ₁-norm formulation as well as a convenient linear programming formulation is explored. These are employed to settle certain conjectures on contrast optimal VCS for the cases k = 4 and 5. Furthermore, for k = 3, we show how block designs can be used to construct VCS which achieve optimality with respect to the average and minimum relative contrasts but require much smaller pixel expansions than the existing ones.     

Optimal quadrature problem on <Emphasis Type="Italic">n</Emphasis>-information for Hardy-Sobolev classes

For β > 0 and an integer r ≥ 2, denote by [(H)\tilde]_￥,b^r\tilde H_{\infty ,\beta }^r those 2π-periodic, real-valued functions f on ℝ, which are analytic in S _β := {z ∈ ℂ: |Im z| < β} and satisfy the restriction |f ^(r)(z)|≤1, z ∈ S _β . The optimal quadrature formulae about information composed of the values of a function and its kth (k = 1, ..., r − 1) derivatives on free knots for the classes [(H)\tilde]_￥,b^r\tilde H_{\infty ,\beta }^r are obtained, and the error estimates of the optimal quadrature formulae are exactly determined.     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

Eigenvalues of the Manifold Sp（n）/U（n）

In this paper, we give the eigenvalues of the manifold Sp(n)/U(n). We prove that an eigenvalue λ _s (f ₂, f ₂, …, f _n ) of the Lie group Sp(n), corresponding to the representation with label (f ₁, f ₂, ..., f _n ), is an eigenvalue of the manifold Sp(n)/U(n), if and only if f ₁, f ₂, …, f _n are all even.     

(<Emphasis Type="Italic">m</Emphasis>,<Emphasis Type="Italic">r</Emphasis>)-central Riordan arrays and their applications

For integers m > r ≥ 0, Brietzke (2008) defined the (m, r)-central coefficients of an infinite lower triangular matrix G = (d, h) = (d_n,k)_n,k∈N as d_{mn+r,(m?1)n+r}, with n = 0, 1, 2,..., and the (m, r)-central coefficient triangle of G as

$${G^{\left( {m,r} \right)}} = {\left( {{d_{mn + r,\left( {m - 1} \right)n + k + r}}} \right)_{n,k \in \mathbb{N}}}.$$

It is known that the (m, r)-central coefficient triangles of any Riordan array are also Riordan arrays. In this paper, for a Riordan array G = (d, h) with h(0) = 0 and d(0), h′(0) ≠ 0, we obtain the generating function of its (m, r)-central coefficients and give an explicit representation for the (m, r)-central Riordan array G^(m,r) in terms of the Riordan array G. Meanwhile, the algebraic structures of the (m, r)-central Riordan arrays are also investigated, such as their decompositions, their inverses, and their recessive expressions in terms of m and r. As applications, we determine the (m, r)-central Riordan arrays of the Pascal matrix and other Riordan arrays, from which numerous identities are constructed by a uniform approach.

     

Omega subgroups of pro-<Emphasis Type="Italic">p</Emphasis> groups

Let G be a pro-p group and let k ≥ 1. If γ _k(p−1) (G) ≤ γ _r for some r and s such that k(p − 1) < r + s(p − 1), we prove that the exponent of Ω_i(G) is at most p ^i+k−1 for all i. Supported by the Spanish Ministry of Science and Education, grant MTM2004-04665, partly with FEDER funds. The first author is also supported by the University of the Basque Country, grant UPV05/99. The second author is also supported by the Basque Government.     

Finite <Emphasis Type="Italic">p</Emphasis>-central groups of height <Emphasis Type="Italic">k</Emphasis>

A finite group G is called p ⁱ -central of height k if every element of order p ⁱ of G is contained in the k ^th -term ζ _k (G) of the ascending central series of G. If p is odd, such a group has to be p-nilpotent (Thm. A). Finite p-central p-groups of height p − 2 can be seen as the dual analogue of finite potent p-groups, i.e., for such a finite p-group P the group P/Ω₁(P) is also p-central of height p − 2 (Thm. B). In such a group P, the index of P ^p is less than or equal to the order of the subgroup Ω₁(P) (Thm. C). If the Sylow p-subgroup P of a finite group G is p-central of height p − 1, p odd, and N _G (P) is p-nilpotent, then G is also p-nilpotent (Thm. D). Moreover, if G is a p-soluble finite group, p odd, and P ∈ Syl _p (G) is p-central of height p − 2, then N _G (P) controls p-fusion in G (Thm. E). It is well-known that the last two properties hold for Swan groups (see [11]).     

On the parity of the class number of an imaginary abelian field of conductor 2<Superscript><Emphasis Type="Italic">a</Emphasis></Superscript><Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">b</Emphasis></Superscript>

Let p be an odd prime number, and p^n₀{p^{n_0}} the highest power of p dividing 2 ^p−1 − 1. Let K_n=Q(z_pⁿ⁺¹){K_n={\bf Q}(\zeta_{p^{n+1}})} and L_n,j=K_n⁺(z_2^j+2){L_{n,j}=K_n^+(\zeta_{2^{j+2}})} for j ≥ 0. Let h_n^*{h_n^*} be the relative class number of K _n , and h _n,j the class number of L _n,j , respectively. Let n be an integer with n ≥ n ₀. We prove that if the ratio h_n^*/h_n-1^*{h_n^*/h_{n-1}^*} is odd, then h _n,j /h _n−1,j is odd for any j ≥ 0.