Abelian covers of graphs and maps between outer automorphism groups of free groups

We explore the existence of homomorphisms between outer automorphism groups of free groups Out(F _n ) → Out(F _m ). We prove that if n > 8 is even and n ≠ m ≤ 2n, or n is odd and n ≠ m ≤ 2n ? 2, then all such homomorphisms have finite image; in fact they factor through det : \({{\rm Out}(F_n) \to \mathbb{Z}/2}\) . In contrast, if m = r ⁿ (n ? 1) + 1 with r coprime to (n ? 1), then there exists an embedding \({{\rm Out}(F_n) \hookrightarrow {\rm Out}(F_m)}\) . In order to prove this last statement, we determine when the action of Out(F _n ) by homotopy equivalences on a graph of genus n can be lifted to an action on a normal covering with abelian Galois group.     

Multiset combinatorial batch codes

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes, are replication-based batch codes in which each server stores a subset of the data items. In this paper, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBC), in which n data items are stored in m servers, such that any multiset request of k items, where any item is requested at most r times, can be retrieved by reading at most t items from each server. The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers, given the values of n, m, k, r, t, which is denoted by N(n, k, m, t; r). We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds on N(n, k, m, t; r) and constructions of MCBCs. In particular, we determine the value of N(n, k, m, 1; r) for any \(n\ge \left\lfloor \frac{k-1}{r}\right\rfloor {m\atopwithdelims ()k-1}-(m-k+1)A(m,4,k-2)\), where \(A(m,4,k-2)\) is the maximum size of a binary constant weight code of length m, distance four and weight \(k-2\). We also determine the exact value of N(n, k, m, 1; r) when \(r\in \{k,k-1\}\) or \(k=m\).     

Dyson’s partition ranks and their multiplicative extensions

We study the Dyson rank function N(r, 3; n), the number of partitions of n with rank \(\equiv r \pmod 3\). We investigate the convexity of these functions. We extend N(r, 3; n) multiplicatively to the set of partitions, and we determine the maximum value when taken over all partitions of size n.     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

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.     

Random embedding of $${\ell_p^n}$$ into $${\ell_r^N}$$

For any 0 < p < 2 and any natural numbers N > n, we give an explicit definition of a random operator \({S : \ell_p^n \to \mathbb{R}^N}\) such that for every 0 < r < p < 2 with r ≤ 1, the operator \({S_r = S : \ell_p^n \to \ell_r^N}\) satisfies with overwhelming probability that \({\|S_r\| \, \|(S_r)_{| {\rm Im}\, S}^{-1}\| \le C(p,r)^{n/(N-n)}}\), where C(p, r) > 0 is a real number depending only on p and r. One of the main tools that we develop is a new type of multidimensional Esseen inequality for studying small ball probabilities.     

Representations of Regular Trees and Invariants of AR-Components for Generalized Kronecker Quivers

We investigate the generalized Kronecker algebra ?? _r = kΓ _r with r ≥ 3 arrows. Given a regular component ?? of the Auslander-Reiten quiver of ?? _r , we show that the quasi-rank rk(??) ∈ ?_≤1 can be described almost exactly as the distance ??(??) ∈ ?₀ between two non-intersecting cones in ??, given by modules with the equal images and the equal kernels property; more precisley, we show that the two numbers are linked by the inequality

$-\mathcal{W}(\mathcal{C}) \leq \text{rk}(\mathcal{C}) \leq - \mathcal{W}(\mathcal{C}) + 3.$

Utilizing covering theory, we construct for each n ∈ ?₀ a bijection φ _n between the field k and {??∣?? regular component, ??(??) = n}. As a consequence, we get new results about the number of regular components of a fixed quasi-rank.

     

Description of polygonal regions by polynomials of bounded degree

We show that every (possibly unbounded) convex polygon P in \({\mathbb{R}^2}\) with m edges can be represented by inequalities p ₁ ≥ 0, . . ., p _n ≥ 0, where the p _i ’s are products of at most k affine functions each vanishing on an edge of P and n = n(m, k) satisfies \({s(m, k) \leq n(m, k) \leq (1+\varepsilon_m) s(m, k)}\) with s(m,k) ? max {m/k, log₂ m} and \({\varepsilon_m \rightarrow 0}\) as \({m \rightarrow \infty}\). This choice of n is asymptotically best possible. An analogous result on representing the interior of P in the form p ₁ > 0, . . ., p _n >  0 is also given. For k ≤ m/log₂ m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k.     

Commutators of Riesz transforms of magnetic Schrödinger operators

Let \({A=-(\nabla-i{\vec a})\cdot (\nabla-i{\vec a}) +V}\) be a magnetic Schrödinger operator acting on \({L^2({\mathbb R}^n)}\), n ≥  1, where \({{\vec a}=(a_1, \ldots, a_n)\in L^2_{\rm loc}({\mathbb R}^n, {\mathbb R}^n)}\) and \({0\leq V\in L^1_{\rm loc}({\mathbb R}^n)}\). In this paper, we show that when a function \({b\in {\rm BMO}({\mathbb R}^n)}\), the commutators [b, T _k ]f = T _k (b f) ? b T _k f, k = 1, . . . , n, are bounded on \({L^p({\mathbb R}^n)}\) for all 1 < p < 2, where the operators T _k are Riesz transforms (?/?x _k  ? i a _k )A ^?1/2 associated with A.     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

Tensor ranks and symmetric tensor ranks are the same for points with low symmetric tensor rank

Fix integers n ≥ 1, d ≥ 2. Let V be an (n + 1)-dimensional vector space over a field with characteristic zero. Fix a symmetric tensor \({T\in S^d(V)\subset V^{\otimes d}}\). Here we prove that the tensor rank of T is equal to its symmetric tensor rank if the latter is at most (d + 1)/2.     

On the Spectrum of the Generalised Petersen Graphs

We show that the gap between the two greatest eigenvalues of the generalised Petersen graphs P(n, k) tends to zero as \(n \rightarrow \infty \). Moreover, we provide explicit upper bounds on the size of this gap. It follows that these graphs have poor expansion properties for large values of n. We also show that there is a positive proportion of the eigenvalues of P(n, k) tending to three.     

Normal coverings of solvable groups

For a finite non cyclic group G, let γ(G) be the smallest integer k such that G contains k proper subgroups H ₁, . . . , H _k with the property that every element of G is contained in \({H_i^g}\) for some \({i \in \{1,\dots,k\}}\) and \({g \in G.}\) We prove that for every n ≥ 2, there exists a finite solvable group G with γ(G) = n.     

Some irreducibility and indecomposability results for truncated binomial polynomials of small degree

In this paper, we show that the truncated binomial polynomials defined by \(P_{n,k}(x)={\sum }_{j=0}^{k} {n \choose j} x^{j}\) are irreducible for each k≤6 and every n≥k+2. Under the same assumption n≥k+2, we also show that the polynomial P _n,k cannot be expressed as a composition P _n,k (x) = g(h(x)) with \(g \in \mathbb {Q}[x]\) of degree at least 2 and a quadratic polynomial \(h \in \mathbb {Q}[x]\). Finally, we show that for k≥2 and m,n≥k+1 the roots of the polynomial P _m,k cannot be obtained from the roots of P _n,k , where m≠n, by a linear map.     

Asymptotic results for jump probabilities associated to the multiple scan statistic

The concept of pattern arises in many applications comprising experimental trials with two or more possible outcomes in each trial. A binary scan of type r / k is a special pattern referring to success–failure strings of fixed length k that contain at least r-successes, where r, k are positive integers with \(r\le k\). The multiple scan statistic \(W_{t,k,r}\) is defined as the enumerating random variable for the overlapping moving windows occurring until trial t which include a scan of type r / k. In the present work, we consider a sequence of independent binary trials with not necessarily equal probabilities of success and develop upper bounds for the probability of the event that the multiple scan statistic will perform a jump from \(\ell \) to \(\ell +1\) (where \(\ell \) is a nonnegative integer) in a finite time horizon.     

Asymptotic analysis on the normalized <Emphasis Type="Italic">k</Emphasis>-error linear complexity of binary sequences

Linear complexity and k-error linear complexity are the important measures for sequences in stream ciphers. This paper discusses the asymptotic behavior of the normalized k-error linear complexity \({L_{n,k}(\underline{s})/n}\) of random binary sequences \({\underline{s}}\) , which is based on one of Niederreiter’s open problems. For k = n θ, where 0 ≤ θ ≤ 1/2 is a fixed ratio, the lower and upper bounds on accumulation points of \({L_{n,k}(\underline{s})/n}\) are derived, which holds with probability 1. On the other hand, for any fixed k it is shown that \({\lim_{n\rightarrow\infty} L_{n,k}(\underline{s})/n = 1/2}\) holds with probability 1. The asymptotic bounds on the expected value of normalized k-error linear complexity of binary sequences are also presented.     

On the value distribution of positive definite quadratic forms

Denote by 0 = λ ₀ < λ ₁ ≤ λ ₂ ≤ . . . the infinite sequence given by the values of a positive definite irrational quadratic form in k variables at integer points. For l ≥ 2 and an (l ?1)-dimensional interval I = I ₂×. . .×I _l we consider the l-level correlation function \({K^{(l)}_I(R)}\) which counts the number of tuples (i ₁, . . . , i _l ) such that \({\lambda_{i_1},\ldots,\lambda_{i_l}\leq R^2}\) and \({\lambda_{i_{j}}-\lambda_{i_{1}}\in I_j}\) for 2 ≤ j ≤ l. We study the asymptotic behavior of \({K^{(l)}_I(R)}\) as R tends to infinity. If k ≥ 4 we prove \({K^{(l)}_I(R)\sim c_l(Q)\,{\rm vol}(I)R^{lk-2(l-1)}}\) for arbitrary l, where c _l (Q) is an explicitly determined constant. This remains true for k = 3 under the restriction l ≤ 3.     

On criteria of estimation of the errors of cubature formulas

The paper considers cubature formulas for calculating integrals of functions f(X), X = (x ₁, …, x _n ) which are defined on the n-dimensional unit hypercube K ⁿ = [0, 1] ⁿ and have integrable mixed derivatives of the kind \(\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)\), 0 ≤ α _j ≤ 2. We estimate the errors R[f] = \(\smallint _{K^n } \) f(X)dX ? Σ _{k = 1} ^N c _k f(X(k)) of cubature formulas (c _k > 0) as functions of the weights c _k of nodes X(k) and properties of integrable functions. The error is estimated in terms of the integrals of the derivatives of f over r-dimensional faces (r≤n) of the hypercube K ⁿ : |R(f)| ≤ \(\sum _{\alpha _j } \) G(α _j )\(\int_{K^r } {\left| {\partial _{\begin{array}{*{20}c} {\alpha _1 \alpha _n } \\ {x_1 , \ldots , x_n } \\ \end{array} } f(X)} \right|} \) dX _r , where coefficients G(α _j ) are criteria which depend only on parameters c _k and X(k). We present an algorithm to calculate these criteria in the two- and n-dimensional cases. Examples are given. A particular case of the criteria is the discrepancy, and the algorithm proposed is a generalization of those used to compute the discrepancy. The results obtained can be used for optimization of cubature formulas as functions of c _k and X(k).     

Generalized modified Gold sequences

In this paper, a large family \({\mathcal{F}^k(l)}\) of binary sequences of period 2 ⁿ ? 1 is constructed for odd n = 2m + 1, where k is any integer with gcd(n, k) = 1 and l is an integer with 1 ≤ l ≤ m. This generalizes the construction of modified Gold sequences by Rothaus. It is shown that \({\mathcal{F}^k(l)}\) has family size \({2^{ln}+2^{(l-1)n}+\cdots+2^n+1}\), maximum nontrivial correlation magnitude 1 + 2^m+l. Based on the theory of quadratic forms over finite fields, all exact correlation values between sequences in \({\mathcal{F}^k(l)}\) are determined. Furthermore, the family \({\mathcal{F}^k(2)}\) is discussed in detail to compute its complete correlation distribution.     

Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If \(V_{1},\ldots , V_{p}\) are the p parts of V(K(n, p)), then a holey k -factor of deficiency \(V_{i}\) of K(n, p) is a k-factor of \(K(n,p)-V_{i}\) for some i satisfying \(1\le i \le p\). Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each \(n \times n\) “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.