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.     

Most small $${\varvec{}}$$-grous have an automorhism of order 2

Let f(p, n) be the number of pairwise nonisomorphic p-groups of order \(p^n\), and let g(p, n) be the number of groups of order \(p^n\) whose automorphism group is a p-group. We prove that the limit, as p grows to infinity, of the ratio g(p, n) / f(p, n) equals 1/3 for \(n=6,7\).     

Coloring of the Square of Kneser Graph $$$$

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n elements set, with two vertices adjacent if they are disjoint. The square \(G^2\) of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in \(G^2\) if the distance between u and v in G is at most 2. Determining the chromatic number of the square of the Kneser graph K(n, k) is an interesting graph coloring problem, and is also related with intersecting family problem. The square of K(2k, k) is a perfect matching and the square of K(n, k) is the complete graph when \(n \ge 3k-1\). Hence coloring of the square of \(K(2k +1, k)\) has been studied as the first nontrivial case. In this paper, we focus on the question of determining \(\chi (K^2(2k+r,k))\) for \(r \ge 2\). Recently, Kim and Park (Discrete Math 315:69–74, 2014) showed that \(\chi (K^2(2k+1,k)) \le 2k+2\) if \( 2k +1 = 2^t -1\) for some positive integer t. In this paper, we generalize the result by showing that for any integer r with \(1 \le r \le k -2\),

1. (a)
   \(\chi (K^2 (2k+r, k)) \le (2k+r)^r\),   if   \(2k + r = 2^t\) for some integer t, and
    
2. (b)
   \(\chi (K^2 (2k+r, k)) \le (2k+r+1)^r\),   if  \(2k + r = 2^t-1\) for some integer t.
    

On the other hand, it was shown in Kim and Park (Discrete Math 315:69–74, 2014) that \(\chi (K^2 (2k+r, k)) \le (r+2)(3k + \frac{3r+3}{2})^r\) for \(2 \le r \le k-2\). We improve these bounds by showing that for any integer r with \(2 \le r \le k -2\), we have \(\chi (K^2 (2k+r, k)) \le 2 \left( \frac{9}{4}k + \frac{9(r+3)}{8} \right) ^r\). Our approach is also related with injective coloring and coloring of Johnson graph.

     

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))\).     

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.     

The Katchalski–Lewis transversal problem for regular polygons

If every k-membered subfamily of a family of plane convex bodies has a line transversal, then we say that this family has property T(k). We say that a family \({\mathcal{F}}\) has property \({T-m}\), if there exists a subfamily \({\mathcal{G} \subset \mathcal{F}}\) with \({|\mathcal{F} - \mathcal{G}| \le m}\) admitting a line transversal. Heppes [7] posed the problem whether there exists a convex body K in the plane such that if \({\mathcal{F}}\) is a finite T(3)-family of disjoint translates of K, then m = 3 is the smallest value for which \({\mathcal{F}}\) has property \({T-m}\). In this paper, we study this open problem in terms of finite T(3)-families of pairwise disjoint translates of a regular 2n-gon \({(n \ge 5)}\). We find out that, for \({5 \le n \le 34}\), the family has property \({T - 3}\) ; for \({n \ge 35}\), the family has property \({T - 2}\).     

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.     

Optimal channel assignment and <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">p</Emphasis>, 1)-labeling

The optimal channel assignment is an important optimization problem with applications in optical networks. This problem was formulated to the L(p, 1)-labeling of graphs by Griggs and Yeh (SIAM J Discrete Math 5:586–595, 1992). A k-L(p, 1)-labeling of a graph G is a function \(f:V(G)\rightarrow \{0,1,2,\ldots ,k\}\) such that \(|f(u)-f(v)|\ge p\) if \(d(u,v)=1\) and \(|f(u)-f(v)|\ge 1\) if \(d(u,v)=2\), where d(u, v) is the distance between the two vertices u and v in the graph. Denote \(\lambda _{p,1}^l(G)= \min \{k \mid G\) has a list k-L(p, 1)-labeling\(\}\). In this paper we show upper bounds \(\lambda _{1,1}^l(G)\le \Delta +9\) and \(\lambda _{2,1}^l(G)\le \max \{\Delta +15,29\}\) for planar graphs G without 4- and 6-cycles, where \(\Delta \) is the maximum vertex degree of G. Our proofs are constructive, which can be turned to a labeling (channel assignment) method to reach the upper bounds.     

On Convex Geometric Graphs with no $$$$ Pairwise Disjoint Edges

A well-known result of Kupitz from 1982 asserts that the maximal number of edges in a convex geometric graph (CGG) on n vertices that does not contain \(k+1\) pairwise disjoint edges is kn (provided \(n>2k\)). For \(k=1\) and \(k=n/2-1\), the extremal examples are completely characterized. For all other values of k, the structure of the extremal examples is far from known: their total number is unknown, and only a few classes of examples were presented, that are almost symmetric, consisting roughly of the kn “longest possible” edges of CK(n), the complete CGG of order n. In order to understand further the structure of the extremal examples, we present a class of extremal examples that lie at the other end of the spectrum. Namely, we break the symmetry by requiring that, in addition, the graph admit an independent set that consists of q consecutive vertices on the boundary of the convex hull. We show that such graphs exist as long as \(q \le n-2k\) and that this value of q is optimal. We generalize our discussion to the following question: what is the maximal possible number f(n, k, q) of edges in a CGG on n vertices that does not contain \(k+1\) pairwise disjoint edges, and, in addition, admits an independent set that consists of q consecutive vertices on the boundary of the convex hull? We provide a complete answer to this question, determining f(n, k, q) for all relevant values of n, k and q.     

A note on Jeśmanowicz’ conjecture

Je?manowicz [9] conjectured that, for positive integers m and n with m > n, gcd(m,n) = 1 and \({m\not\equiv n\pmod{2}}\), the exponential Diophantine equation \({(m^2-n^2)^x+(2mn)^y=(m^2+n^2)^z}\) has only the positive integer solution (x, y, z) = (2, 2, 2). We prove the conjecture for \({2 \| mn}\) and m + n has a prime factor p with \({p\not\equiv1\pmod{16}}\).     

Interlacing of zeros of Gegenbauer polynomials of non-consecutive degree from different sequences

A theorem due to Stieltjes’ states that if \({\{p_n\}_{n=0}^\infty}\) is any orthogonal sequence then, between any two consecutive zeros of p _k , there is at least one zero of p _n whenever k < n, a property called Stieltjes interlacing. We show that Stieltjes interlacing extends to the zeros of Gegenbauer polynomials \({C_{n+1}^{\lambda}}\) and \({C_{n-1}^{\lambda+t}}\), \({\lambda > -\frac 12}\), if 0 < t ≤ k + 1, and also to the zeros of \({C_{n+1}^{\lambda}}\) and \({C_{n-2}^{\lambda +k}}\) if \({k\in\{1,2,3\}}\). More generally, we prove that Stieltjes interlacing holds between the zeros of the kth derivative of \({C_{n}^{\lambda}}\) and the zeros of \({C_{n+1}^{\lambda}}\), \({k\in\{1,2,\dots,n-1\}}\) and we derive associated polynomials that play an analogous role to the de Boor–Saff polynomials in completing the interlacing process of the zeros.     

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\).     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

2-Arc-transitive cyclic covers of $$K_{n,n}$$

In this paper, a complete classification is achieved of all the regular covers of the complete bipartite graphs \(K_{n,n}\) with cyclic covering transformation group, whose fibre-preserving automorphism group acts 2-arc-transitively. All these covers consist of one threefold covers of \(K_{6,6}\), one twofold cover of \(K_{12, 12}\) and one infinite family X(r, p) of p-fold covers of \(K_{p^r,p^r}\) with p a prime and r an integer such that \(p^r\ge 3\). This infinite family X(r, p) can be derived by a very simple and nice voltage assignment f as follows: \(X(r, p)=K_{p^r, p^r}\times _f \mathbb {Z}_p\), where \(K_{p^r, p^r}\) is a complete bipartite graph with the bipartition \(V=\{ \alpha \bigm |\alpha \in V(r,p)\}\cup \{ \alpha '\bigm |\alpha \in V(r,p)\}\) for the r-dimensional vector space V(r, p) over the field of order p and \(f_{\alpha ,\beta '}=\sum _{i=1}^ra_ib_i,\,\, \mathrm{for\,\,all}\,\,\alpha =(a_i)_r, \beta =(b_i)_r\in V(r,p)\).     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

Sets with even partition functions and 2-adic integers

For P ? \(\mathbb{F}_2 \)[z] with _P(0) = 1 and deg(_P) ≥ 1, let \(\mathcal{A}\) = \(\mathcal{A}\)(P) (cf. [4], [5], [13]) be the unique subset of ? such that Σ _n≥0 p(\(\mathcal{A}\), n)z ⁿ ≡ P(z) (mod 2), where p(\(\mathcal{A}\), n) is the number of partitions of n with parts in \(\mathcal{A}\). Let p be an odd prime and P ? \(\mathbb{F}_2 \)[z] be some irreducible polynomial of order p, i.e., p is the smallest positive integer such that P(z) divides 1 + z ^p in \(\mathbb{F}_2 \)[z]. In this paper, we prove that if m is an odd positive integer, the elements of \(\mathcal{A}\) = \(\mathcal{A}\)(P) of the form 2 ^k m are determined by the 2-adic expansion of some root of a polynomial with integer coefficients. This extends a result of F. Ben Saïd and J.-L. Nicolas [6] to all primes p.     

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.     

A Formula for the Partition Function That “Counts”

We derive a combinatorial multisum expression for the number D(n, k) of partitions of n with Durfee square of order k. An immediate corollary is therefore a combinatorial formula for p(n), the number of partitions of n. We then study D(n, k) as a quasipolynomial. We consider the natural polynomial approximation \({\tilde{D}(n, k)}\) to the quasipolynomial representation of D(n, k). Numerically, the sum \({\sum_{1\leq k \leq \sqrt{n}} \tilde{D}(n, k)}\) appears to be extremely close to the initial term of the Hardy-Ramanujan-Rademacher convergent series for p(n).     

O n ( m n,n, m n,m) relative differe nce sets with $$\text {gcd}( m,n)=1$$gcd( m,n)=1

There has been much research on \((p^{a},p^{b},p^{a},p^{a-b})\) relative difference sets with p a prime, while there are only a few results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\). The non-existence results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\) have only been obtained for the following five cases: (1) \(m=p,\ n=q,\ p>q\); (2) \(m=pq,\ n=3,\ p,q>3\); (3) \(m=4,\ n=p\); (4) \(m=2\) and (5) \(n=p\), where p, q are distinct odd primes. For the existence results, there are only four constructions of semi-regular relative difference sets in groups of size not a prime power with the forbidden subgroup having size larger than 2. In this paper, we present some more non-existence results on (mn, n, mn, m) relative difference sets with \(\text {gcd}(m,n)=1\). In particular, our result is a generalization of the main result of Hiramine’s work (J Comb Theory Ser A 117(7):996–1003, 2010). Meanwhile, we give a construction of non-abelian (16q, q, 16q, 16) relative difference sets, where q is a prime power with \(q\equiv 1\pmod {4}\) and \(q>4.2\times 10^{8}\). This is the third known infinite classes of non-abelian semi-regular relative difference sets.