Finite Gap Jacobi Matrices,III. Beyond the Szegő Class

Let \({\frak {e}}\subset {\mathbb {R}}\) be a finite union of ?+1 disjoint closed intervals, and denote by ω _j the harmonic measure of the j left-most bands. The frequency module for \({\frak {e}}\) is the set of all integral combinations of ω ₁,…,ω _? . Let \(\{\tilde{a}_{n}, \tilde{b}_{n}\}_{n=-\infty}^{\infty}\) be a point in the isospectral torus for \({\frak {e}}\) and \(\tilde{p}_{n}\) its orthogonal polynomials. Let \(\{a_{n},b_{n}\}_{n=1}^{\infty}\) be a half-line Jacobi matrix with \(a_{n} = \tilde{a}_{n} + \delta a_{n}\), \(b_{n} = \tilde{b}_{n} +\delta b_{n}\). Suppose

$\sum_{n=1}^\infty \lvert \delta a_n\rvert ^2 + \lvert \delta b_n\rvert ^2 <\infty $

and \(\sum_{n=1}^{N} e^{2\pi i\omega n} \delta a_{n}\), \(\sum_{n=1}^{N} e^{2\pi i\omega n} \delta b_{n}\) have finite limits as N→∞ for all ω in the frequency module. If, in addition, these partial sums grow at most subexponentially with respect to ω, then for z∈???, \(p_{n}(z)/\tilde{p}_{n}(z)\) has a limit as n→∞. Moreover, we show that there are non-Szeg? class J’s for which this holds.

     

An Extension of the Fermat-Torricelli Problem

The Fermat-Torricelli problem is an optimization problem associated with a finite subset \(\{a_{j}\}_{j=1}^{q}\) of ? ^N and a family \(\{c_{j}\}_{j=1}^{q}\) of positive weights. The function F to be minimized is defined by \(F(x)=\sum _{j=1}^{q}c_{j}\Vert x-a_{j}\Vert\). In this paper, we extend this problem to the case of volumes.     

Idempotent and <Emphasis Type="Italic">p</Emphasis>-potent quadratic functions: distribution of nonlinearity and co-dimension

The Walsh transform \(\widehat{Q}\) of a quadratic function \(Q:{\mathbb F}_{p^n}\rightarrow {\mathbb F}_p\) satisfies \(|\widehat{Q}(b)| \in \{0,p^{\frac{n+s}{2}}\}\) for all \(b\in {\mathbb F}_{p^n}\), where \(0\le s\le n-1\) is an integer depending on Q. In this article, we study the following three classes of quadratic functions of wide interest. The class \(\mathcal {C}_1\) is defined for arbitrary n as \(\mathcal {C}_1 = \{Q(x) = \mathrm{Tr_n}(\sum _{i=1}^{\lfloor (n-1)/2\rfloor }a_ix^{2^i+1})\;:\; a_i \in {\mathbb F}_2\}\), and the larger class \(\mathcal {C}_2\) is defined for even n as \(\mathcal {C}_2 = \{Q(x) = \mathrm{Tr_n}(\sum _{i=1}^{(n/2)-1}a_ix^{2^i+1}) + \mathrm{Tr_{n/2}}(a_{n/2}x^{2^{n/2}+1}) \;:\; a_i \in {\mathbb F}_2\}\). For an odd prime p, the subclass \(\mathcal {D}\) of all p-ary quadratic functions is defined as \(\mathcal {D} = \{Q(x) = \mathrm{Tr_n}(\sum _{i=0}^{\lfloor n/2\rfloor }a_ix^{p^i+1})\;:\; a_i \in {\mathbb F}_p\}\). We determine the generating function for the distribution of the parameter s for \(\mathcal {C}_1, \mathcal {C}_2\) and \(\mathcal {D}\). As a consequence we completely describe the distribution of the nonlinearity for the rotation symmetric quadratic Boolean functions, and in the case \(p > 2\), the distribution of the co-dimension for the rotation symmetric quadratic p-ary functions, which have been attracting considerable attention recently. Our results also facilitate obtaining closed formulas for the number of such quadratic functions with prescribed s for small values of s, and hence extend earlier results on this topic. We also present the complete weight distribution of the subcodes of the second order Reed–Muller codes corresponding to \(\mathcal {C}_1\) and \(\mathcal {C}_2\) in terms of a generating function.     

On the Dual Form of ‘Low <Emphasis Type="Italic">M</Emphasis><Superscript>*</Superscript> Estimate’ in the Quasi-convex Case

Let\(B_{2}^{n}\) denote the Euclidean ball in\({\mathbb R}^n\), and, given closed star-shaped body\(K \subset {\mathbb R}^{n}, M_{K}\) denote the average of the gauge of K on the Euclidean sphere. Let\(p \in (0,1)\) and let\(K \subset {\mathbb R}^{n}\) be a p-convex body. In [17] we proved that for every\(\lambda \in (0,1)\) there exists an orthogonal projection P of rank\((1 - \lambda)n\) such that

$\frac{f(\lambda)}{M_K} PB^{n}_{2} \subset PK,$

where\(f(\lambda)=c_p\lambda^{1+1/p}\) for some positive constant c _p depending on p only. In this note we prove that\(f(\lambda)\) can be taken equal to\(C_p\lambda^{1/p-1/2}\). In terms of Kolmogorov numbers it means that for every\(k \leq n\)

$d_k (\hbox{Id}:\ell^{n}_{2} \to ({\mathbb R}^{n},\|\cdot\|_{K})) \leq C_p \frac{n^{1/p-1}}{k^{1/p-1/2}} \ell(\hbox{ID}: \ell^{n}_{2} \to ({\mathbb R}^{n}, \|\cdot\|_{K})),$

where\(\ell(\hbox{Id})={\bf E}\|\sum\limits^{n}_{i=1}g_i e_i\|_K\) for the independent standard Gaussian random variables\(\{g_i\}\) and the canonical basis\(\{e_i\}\) of\({\mathbb R}^n\). All results do not require the symmetry of K.

     

Frame completions with prescribed norms: local minimizers and applications

Let \(\mathcal {F}_{0}=\{f_{i}\}_{i\in \mathbb {I}_{n_{0}}}\) be a finite sequence of vectors in \(\mathbb {C}^{d}\) and let \(\mathbf {a}=(a_{i})_{i\in \mathbb {I}_{k}}\) be a finite sequence of positive numbers, where \(\mathbb {I}_{n}=\{1,\ldots , n\}\) for \(n\in \mathbb {N}\). We consider the completions of \(\mathcal {F}_{0}\) of the form \(\mathcal {F}=(\mathcal {F}_{0},\mathcal {G})\) obtained by appending a sequence \(\mathcal {G}=\{g_{i}\}_{i\in \mathbb {I}_{k}}\) of vectors in \(\mathbb {C}^{d}\) such that ∥g _i ∥² = a _i for \(i\in \mathbb {I}_{k}\), and endow the set of completions with the metric \(d(\mathcal {F},\tilde {\mathcal {F}}) =\max \{ \,\|g_{i}-\tilde {g}_{i}\|: \ i\in \mathbb {I}_{k}\}\) where \(\tilde {\mathcal {F}}=(\mathcal {F}_{0},\,\tilde {\mathcal {G}})\). In this context we show that local minimizers on the set of completions of a convex potential P _φ , induced by a strictly convex function φ, are also global minimizers. In case that φ(x) = x ² then P _φ is the so-called frame potential introduced by Benedetto and Fickus, and our work generalizes several well known results for this potential. We show that there is an intimate connection between frame completion problems with prescribed norms and frame operator distance (FOD) problems. We use this connection and our results to settle in the affirmative a generalized version of Strawn’s conjecture on the FOD.     

Inequalities between Dirichlet and Neumann eigenvalues of vibrating strings

The Dirichlet eigenvalues \({\{\lambda_{n}\}_{n=1}^{\infty}}\) and Neumann eigenvalues \({\{\mu_{n}\}_{n=1}^{\infty}}\) of the string equation \({\varphi'' (x) +\lambda \rho (x) \varphi(x) =0}\) are considered. It is known that \({ \mu_{n} < \lambda_{n} < \mu_{n+2}}\) for all n. The purpose of this paper is to provide conditions on the mass density \({\rho(x)}\) under which \({\lambda_{n} < \mu_{n+1}}\) or \({\mu_{n+1} < \lambda_{n}.}\)     

An Erdös–Révész Type Law of the Iterated Logarithm for Order Statistics of a Stationary Gaussian Process

Let \(\{X(t):t\in \mathbb R_+\}\) be a stationary Gaussian process with almost surely (a.s.) continuous sample paths, \(\mathbb E X(t) = 0, \mathbb E X^2(t) = 1\) and correlation function satisfying (i) \(r(t) = 1 - C|t|^{\alpha } + o(|t|^{\alpha })\) as \(t\rightarrow 0\) for some \(0\le \alpha \le 2\) and \(C>0\); (ii) \(\sup _{t\ge s}|r(t)|<1\) for each \(s>0\) and (iii) \(r(t) = O(t^{-\lambda })\) as \(t\rightarrow \infty \) for some \(\lambda >0\). For any \(n\ge 1\), consider n mutually independent copies of X and denote by \(\{X_{r:n}(t):t\ge 0\}\) the rth smallest order statistics process, \(1\le r\le n\). We provide a tractable criterion for assessing whether, for any positive, non-decreasing function \(f, \mathbb P(\mathscr {E}_f)=\mathbb P(X_{r:n}(t) > f(t)\, \text { i.o.})\) equals 0 or 1. Using this criterion we find, for a family of functions \(f_p(t)\) such that \(z_p(t)=\mathbb P(\sup _{s\in [0,1]}X_{r:n}(s)>f_p(t))=O((t\log ^{1-p} t)^{-1})\), that \(\mathbb P(\mathscr {E}_{f_p})= 1_{\{p\ge 0\}}\). Consequently, with \(\xi _p (t) = \sup \{s:0\le s\le t, X_{r:n}(s)\ge f_p(s)\}\), for \(p\ge 0\) we have \(\lim _{t\rightarrow \infty }\xi _p(t)=\infty \) and \(\limsup _{t\rightarrow \infty }(\xi _p(t)-t)=0\) a.s. Complementarily, we prove an Erdös–Révész type law of the iterated logarithm lower bound on \(\xi _p(t)\), namely, that \(\liminf _{t\rightarrow \infty }(\xi _p(t)-t)/h_p(t) = -1\) a.s. for \(p>1\) and \(\liminf _{t\rightarrow \infty }\log (\xi _p(t)/t)/(h_p(t)/t) = -1\) a.s. for \(p\in (0,1]\), where \(h_p(t)=(1/z_p(t))p\log \log t\).     

Schatten-Herz Operators,Berezin Transform and Mixed Norm Spaces

For p, q > 0 we study operators T on the Bergman space \({A_{2}(\mathbb{D)}}\) in the disk such that \({\left(\sum_{j}\Vert T\Delta_{j}\Vert_{p}^{q}\right)^{1/q}<\infty,}\) where the norms \({\Vert\cdot\Vert_{p}}\) are in the Schatten class S _p (A ₂), the projection \({\Delta_{j}f=\sum_{n\in I_{j}}a_{n}z^{n}}\) for \({f(z)=\sum_{n=0}^{\infty}a_{n}z^{n}}\) and \({I_{j}=[2^{j}-1,2^{j+1} )\cap(\mathbb{N}\cup\{0\})}\) for \({j\in\mathbb{N}\cup\{0\}.}\) We consider the relation of this property with mixed norms of the Berezin transform of T and of the related function \({f_{T}(z)={\Vert}T(k_{z})\Vert}\) where k _z is the normalized Bergman kernel. These classes of operators denoted by S(p, q) are closely related when assumed to be positive with other sets of operators, like the class of positive operators on A ₂ for which \({\left(\sum_{j\geq0}(\sum_{n\in I_{j}}|\left\langle T^pe_{n},e_{n}\right\rangle |)^{q/p}\right)^{1/q}<\infty}\) , where \({\{e_{n}\}_{n\geq0}}\) is the canonical basis of A ₂; also we study the relation of Toeplitz operators in S(p, q) with the Schatten-Herz classes, where the decomposition is through dyadic annuli of the domain \({\mathbb{D}}\) .     

On behavior of Fourier coefficients by Walsh system

The paper proves that for any ε > 0 there exists ameasurable set E ? [0, 1] with measure |E| > 1 ? ε such that for each f ∈ L¹[0, 1] there is a function \(\tilde f \in {L^1}\left[ {0,1} \right]\) coinciding with f on E whose Fourier-Walsh series converges to \(\tilde f\) in L¹[0, 1]-norm, and the sequence \(\left\{ {\left| {{c_k}\left( {\tilde f} \right)} \right|} \right\}_{n = 0}^\infty \) is monotonically decreasing, where \(\left\{ {{c_k}\left( {\tilde f} \right)} \right\}\) is the sequence of Fourier-Walsh coefficients of \(\left\{ {\left| {{c_k}\left( {\tilde f} \right)} \right|} \right\}_{n = 0}^\infty \).     

Spectrality of infinite convolutions with three-element digit sets

Let \(0< \rho <1\) and let \(\{a_n, b_n\}_{n=1}^\infty \) be a sequence of integers with bounded from upper and lower. Associated with them there exists a unique Borel probability measure \(\mu _{\rho , \{0, a_n, b_n\}}\) generated by the following infinite convolution product

$$\begin{aligned} \mu _{\rho , \{0, a_n, b_n\}}=\delta _{\rho \{0, a_1, b_1\}} *\delta _{\rho ^2 \{0, a_2, b_2\}} *\delta _{\rho ^3 \{0, a_3, b_3\}} *\cdots \end{aligned}$$

in the weak convergence, where \(\delta _E=\frac{1}{\# E}\sum _{e \in E} \delta _e\) and \(\hbox {gcd}(a_n, b_n)=1\) for all \(n \in {{\mathbb {N}}}\). In this paper, we show that \(L^2(\mu _{\rho , \{0, a_n, b_n\}})\) admits an exponential orthonormal basis if and only if \(\rho ^{-1} \in 3{{\mathbb {N}}}\) and  \(\{a_n, b_n\} \equiv \{1, 2\} \ (\mathrm {mod} \ 3)\) for all \(n \in {{\mathbb {N}}}\).

     

New optical orthogonal signature pattern codes with maximum collision parameter 2 and weight 4

Optical orthogonal signature pattern codes (OOSPCs) play an important role in a novel type of optical code-division multiple-access network for 2-dimensional image transmission. There is a one-to-one correspondence between an \((m, n, w, \lambda )\)-OOSPC and a \((\lambda +1)\)-(mn, w, 1) packing design admitting an automorphism group isomorphic to \(\mathbb {Z}_m\times \mathbb {Z}_n\). In 2010, Sawa gave a construction of an (m, n, 4, 2)-OOSPC from a one-factor of Köhler graph of \(\mathbb {Z}_m\times \mathbb {Z}_n\) which contains a unique element of order 2. In this paper, we study the existence of one-factor of Köhler graph of \(\mathbb {Z}_m\times \mathbb {Z}_n\) having three elements of order 2. It is proved that there is a one-factor in the Köhler graph of \(\mathbb {Z}_{2^{\epsilon }p}\times \mathbb {Z}_{2^{\epsilon '}}\) relative to the Sylow 2-subgroup if there is an S-cyclic Steiner quadruple system of order 2p, where \(p\equiv 5\pmod {12}\) is a prime and \(1\le \epsilon ,\epsilon '\le 2\). Using this one-factor, we construct a strictly \(\mathbb {Z}_{2^{\epsilon }p}\times \mathbb {Z}_{2^{\epsilon '}}\)-invariant regular \(G^*(p,2^{\epsilon +\epsilon '},4,3)\) relative to the Sylow 2-subgroup. By using the known S-cyclic SQS(2p) and a recursive construction for strictly \(\mathbb {Z}_{m}\times \mathbb {Z}_{n}\)-invariant regular G-designs, we construct more strictly \(\mathbb {Z}_{m}\times \mathbb {Z}_{n}\)-invariant 3-(mn, 4, 1) packing designs. Consequently, there is an optimal \((2^{\epsilon }m,2^{\epsilon '}n,4,2)\)-OOSPC for any \(\epsilon ,\epsilon '\in \{0,1,2\}\) with \(\epsilon +\epsilon '>0\) and an optimal (6m, 6n, 4, 2)-OOSPC where m, n are odd integers whose all prime divisors from the set \(\{p\equiv 5\pmod {12}:p\) is a prime, \(p<\)1,500,000}.     

A characterization of the normal distribution using stationary max-stable processes

Consider a max-stable process of the form \(\eta (t) = \max _{i\in \mathbb {N}} U_{i} \mathrm {e}^{\langle X_{i}, t\rangle - \kappa (t)}\), \(t\in \mathbb {R}^{d}\), where \(\{U_{i}, i\in \mathbb {N}\}\) are points of the Poisson process with intensity u ^?2du on (0,∞), X _i , \(i\in \mathbb {N}\), are independent copies of a random d-variate vector X (that are independent of the Poisson process), and \(\kappa :\mathbb {R}^{d} \to \mathbb {R}\) is a function. We show that the process η is stationary if and only if X has multivariate normal distribution and κ(t)?κ(0) is the cumulant generating function of X. In this case, η is a max-stable process introduced by R. L. Smith.     

Birational rigidity of complete intersections

We prove that every smooth complete intersection \(X=X_{d_{1}, \ldots , d_{s}}\subset \mathbb {P}^{\sum _{i=1}^{s}d_{i}}\) defined by s hypersurfaces of degree \(d_{1}, \ldots , d_{s}\) is birationally superrigid if \(5s +1\le \frac{2(\sum _{i=1}^{s}d_{i}+1)}{\sqrt{\prod _{i=1}^{s}d_{i}}}\). In particular, X is non-rational and \({{\mathrm{Bir}}}(X)={{\mathrm{Aut}}}(X)\). We also prove birational superrigidity of singular complete intersections with similar numerical condition. These extend the results proved by Tommaso de Fernex.     

Generalization of the non-local derangement identity and applications to multiple zeta-type series

The goal of this paper is the study of a transformation concerning the general K-fold finite sums of the form

$$\begin{aligned} \sum _{N\ge n_1\ge \cdots \ge n_K\ge 1}\frac{1}{b_{n_K}}\cdot \prod _{j=1}^{K-1}\frac{1}{a_{n_j}}, \end{aligned}$$

where \((K,N)\in \mathbb {N}^2\) and \(\{a_n\}_{n=1}^{\infty }\), \(\{b_n\}_{n=1}^{\infty }\) are appropriate real sequences. In the application part of our paper we apply the developed transformation to two special parametric multiple zeta-type series that generalize the well-know formula \(\zeta ^\star (\{2\}_K,1)=2\zeta (2K+1)\), \(K\in \mathbb {N}\). As a corollary of our parametric results, we also prove several sum formulas involving multiple zeta-star values.

     

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.     

On geometric properties of the generating function for the Ramanujan sequence

The Ramanujan sequence \(\{\theta _{n}\}_{n \ge 0}\), defined as \(\theta _{0}= {1}/{2}\), \({n^{n}} \theta _{n}/{n !} = {e^{n}}/{2} - \sum _{k=0}^{n-1} {n^{k}}/{k !}\, \), \(n \ge 1\), has been studied on many occasions and in many different contexts. Adell and Jodrá (Ramanujan J 16:1–5, 2008) and Koumandos (Ramanujan J 30:447–459, 2013) showed, respectively, that the sequences \(\{\theta _{n}\}_{n \ge 0}\) and \(\{4/135 - n \cdot (\theta _{n}- 1/3 )\}_{n \ge 0}\) are completely monotone. In the present paper, we establish that the sequence \(\{(n+1) (\theta _{n}- 1/3 )\}_{n \ge 0}\) is also completely monotone. Furthermore, we prove that the analytic function \((\theta _{1}- 1/3 )^{-1}\sum _{n=1}^{\infty } (\theta _{n}- 1/3 ) z^{n} / n^{\alpha }\) is universally starlike for every \(\alpha \ge 1\) in the slit domain \(\mathbb {C}\setminus [1,\infty )\). This seems to be the first result putting the Ramanujan sequence into the context of analytic univalent functions and is a step towards a previous stronger conjecture, proposed by Ruscheweyh et al. (Israel J Math 171:285–304, 2009), namely that the function \((\theta _{1}- 1/3 )^{-1}\sum _{n=1}^{\infty } (\theta _{n}- 1/3 ) z^{n} \) is universally convex.     

Singular Values Distribution of Squares of Elliptic Random Matrices and Type B Narayana Polynomials

We consider Gaussian elliptic random matrices X of a size \(N \times N\) with parameter \(\rho \), i.e., matrices whose pairs of entries \((X_{ij}, X_{ji})\) are mutually independent Gaussian vectors with \(\mathbb {E}\,X_{ij} = 0\), \(\mathbb {E}\,X^2_{ij} = 1\) and \(\mathbb {E}\,X_{ij} X_{ji} = \rho \). We are interested in the asymptotic distribution of eigenvalues of the matrix \(W =\frac{1}{N^2} X^2 X^{*2}\). We show that this distribution is determined by its moments, and we provide a recurrence relation for these moments. We prove that the (symmetrized) asymptotic distribution is determined by its free cumulants, which are Narayana polynomials of type B:

$$\begin{aligned} c_{2n} = \sum _{k=0}^n {\left( {\begin{array}{c}n\\ k\end{array}}\right) }^2 \rho ^{2k}. \end{aligned}$$

     

Fourth-order Schrödinger type operator with singular potentials

We prove that a deformation of a hypersurface in an (n + 1)-dimensional real space form \({{\mathbb S}^{n+1}_{p,1}}\) induces a Hamiltonian variation of the normal congruence in the space \({{\mathbb L}({\mathbb S}^{n+1}_{p,1})}\) of oriented geodesics. As an application, we show that every Hamiltonian minimal submanifold in \({{\mathbb L}({\mathbb S}^{n+1})}\) (resp. \({{\mathbb L}({\mathbb H}^{n+1})}\)) with respect to the (para-)Kähler Einstein structure is locally the normal congruence of a hypersurface \({\Sigma}\) in \({{\mathbb S}^{n+1}}\) (resp. \({{\mathbb H}^{n+1}}\)) that is a critical point of the functional \({{\mathcal W}(\Sigma) = \int_\Sigma\left(\Pi_{i=1}^n|\epsilon+k_i^2|\right)^{1/2}}\), where k_i denote the principal curvatures of \({\Sigma}\) and \({\epsilon \in \{-1, 1\}}\). In addition, for \({n = 2}\), we prove that every Hamiltonian minimal surface in \({{\mathbb L}({\mathbb S}^{3})}\) (resp. \({{\mathbb L}({\mathbb H}^{3})}\)), with respect to the (para-)Kähler conformally flat structure, is the normal congruence of a surface in \({{\mathbb S}^{3}}\) (resp. \({{\mathbb H}^{3}}\)) that is a critical point of the functional \({{\mathcal W}\prime(\Sigma) = \int_\Sigma\sqrt{H^2-K+1}}\) (resp. \({{\mathcal W}\prime(\Sigma) = \int_\Sigma\sqrt{H^2-K-1}}\)), where H and K denote, respectively, the mean and Gaussian curvature of \({\Sigma}\).     

Group divisible designs with large block sizes

For positive integers n, k with \(3\le k\le n\), let \(X=\mathbb {F}_{2^n}\setminus \{0,1\}\), \({\mathcal {G}}=\{\{x,x+1\}:x\in X\}\), and \({\mathcal {B}}_k=\left\{ \{x_1,x_2,\ldots ,x_k\}\!\subset \!X:\sum \limits _{i=1}^kx_i=1,\ \sum \limits _{i\in I}x_i\!\ne \!1\ \mathrm{for\ any}\ \emptyset \!\ne \!I\!\subsetneqq \!\{1,2,\ldots ,k\}\right\} \). Lee et al. used the inclusion–exclusion principle to show that the triple \((X,{\mathcal {G}},{\mathcal {B}}_k)\) is a \((k,\lambda _k)\)-GDD of type \(2^{2^{n-1}-1}\) for \(k\in \{3,4,5,6,7\}\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(2^n-2^i)}{(k-2)!}\) (Lee et al. in Des Codes Cryptogr,  https://doi.org/10.1007/s10623-017-0395-8, 2017). They conjectured that \((X,{\mathcal {G}},{\mathcal {B}}_k)\) is also a \((k,\lambda _k)\)-GDD of type \(2^{2^{n-1}-1}\) for any integer \(k\ge 8\). In this paper, we use a similar construction and counting principles to show that there is a \((k,\lambda _k)\)-GDD of type \((q^2-q)^{(q^{n-1}-1)/(q-1)}\) for any prime power q and any integers k, n with \(3\le k\le n\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(q^n-q^i)}{(k-2)!}\). Consequently, their conjecture holds. Such a method is also generalized to yield a \((k,\lambda _k)\)-GDD of type \((q^{\ell +1}-q^{\ell })^{(q^{n-\ell }-1)/(q-1)}\) where \(\lambda _k=\frac{\prod _{i=3}^{k-1}(q^n-q^{\ell +i-1})}{(k-2)!}\) and \(k+\ell \le n+1\).     

A Unified Framework for Linear Dimensionality Reduction in L1

For a family of interpolation norms \({\| \cdot \|_{1,2,s}}\) on \({\mathbb{R}^{n}}\), we provide a distribution over random matrices \({\Phi_s \in \mathbb{R}^{m \times n}}\) parametrized by sparsity level s such that for a fixed set X of K points in \({\mathbb{R}^{n}}\), if \({m \geq C s \log(K)}\) then with high probability, \({\frac{1}{2}\| \varvec{x} \|_{1,2,s} \leq \| \Phi_s (\varvec{x}) \|_1 \leq 2 \| \varvec{x} \|_{1,2,s}}\) for all \({\varvec{x} \in X}\). Several existing results in the literature roughly reduce to special cases of this result at different values of s: For s = n, \({\| \varvec{x} \|_{1,2,n}\equiv \| \varvec{x} \|_{1}}\) and we recover that dimension reducing linear maps can preserve the ?₁-norm up to a distortion proportional to the dimension reduction factor, which is known to be the best possible such result. For s = 1, \({\| \varvec{x} \|_{1,2,1}\equiv \| \varvec{x} \|_{2}}\), and we recover an ?₂/?₁ variant of the Johnson–Lindenstrauss Lemma for Gaussian random matrices. Finally, if \({\varvec{x}}\) is s- sparse, then \({\| \varvec{x} \|_{1,2,s} = \| \varvec{x} \|_1}\) and we recover that s-sparse vectors in \({\ell_1^n}\) embed into \({\ell_1^{\mathcal{O}(s \log(n))}}\) via sparse random matrix constructions.