In [Fr2, Skr], Frolov and Skriganov showed that low discrepancy point sets in the multidimensional unit cube $[0,1{)}^s$ can be obtained from admissible lattices in ${\mathbb{R}}^s$. In this paper, we get a similar result for the case of $({\mathbb{F}}_q((x^{-1})){)}^s$. Then we combine this approach with Halton’s construction of low discrepancy sequences.

Let ${\mathcal{P}}_N(\mathbb{R})$ be the space of all real polynomials in $N$ variables with the usual inner product $⟨\cdot ,\cdot ⟩$ on it, given by integrating over the unit sphere. We start by deriving an explicit combinatorial formula for the bilinear form representing this inner product on the space of coefficient vectors of all polynomials in ${\mathcal{P}}_N(\mathbb{R})$ of degree $\le M$. We exhibit two applications of this formula. First, given a finite-dimensional subspace $V$ of ${\mathcal{P}}_N(\mathbb{R})$ defined over $\mathbb{Q}$, we prove the existence of an orthogonal basis for $(V,⟨\cdot ,\cdot ⟩)$, consisting of polynomials of small height with integer coefficients, providing an explicit bound on the height; this can be viewed as a version of Siegel’s lemma for real polynomial inner product spaces. Secondly, we derive a criterion for a finite set of points on the unit sphere in ${\mathbb{R}}^N$ to be a spherical $M$-design.

A digital search tree (DST) – one of the most fundamental data structures on words – is a digital tree in which keys (strings, words) are stored directly in (internal) nodes. The profile of a digital search tree is a parameter that counts the number of nodes at the same distance from the root. It is a function of the number of nodes and the distance from the root. Several tree parameters, such as height, size, depth, shortest path, and fill-up level, can be uniformly analyzed through the profile. In this note we analyze asymptotically the average profile for a symmetric digital search tree in which strings are generated by an unbiased memoryless source. We show that the average profile undergoes several phase transitions: initially it resembles a full tree until it starts growing algebraically with the number of nodes, and then it decays first algebraically, then exponentially, and finally quadratic exponentially. We derive these results by a combinational of analytic techniques, such as the saddle point method.

A Hankel operator $H=[h_{i+j}]$ can be factored as $H=M{M}^{\ast }$, where $M$ maps a space of $L^2$ functions to the corresponding moment sequences. Furthermore, a necessary and sufficient condition for a sequence to be in the range of $M$ can be expressed in terms of an expansion in orthogonal polynomials. Combining these two results yields a wealth of combinatorial identities that incorporate both the matrix entries $h_{i+j}$ and the coefficients of the orthogonal polynomials.

In the paper, we are studying some properties of subsets $Q\subseteq {\mathrm{\Lambda }}_1+\cdots +{\mathrm{\Lambda }}_k$, where ${\mathrm{\Lambda }}_i$ are dissociated sets. The exact upper bound for the number of solutions of the following equation:
$$\begin{array}{}\text{(1)}& q_1+\cdots +q_p=q_{p+1}+\cdots +q_{2p},q_i\in Q\end{array}$$
in groups ${\mathbb{F}}_2^n$ is found. Using our approach, we easily prove a recent result of J. Bourgain on sets of large exponential sums and obtain a tiny improvement of his theorem. Besides, an inverse problem is considered in the article. Let $Q$ be a set belonging to a subset of two dissociated sets such that equation (1) has many solutions. We prove that in this case, a large proportion of $Q$ is highly structured.

We classify compositions avoiding a single permutation pattern of type (2, 1) according to
Wilf-equivalence and give the generating function for each of the Wilf classes.

Let $m,n\ge 1$ be integers. Define ${\mathcal{T}}_{m,n}$ to be the <i>transportation polytope</i> consisting of the $m\times n$ non-negative real matrices whose rows each sum to $1$ and whose columns each sum to $m/n$. The special case ${\mathcal{B}}_n={\mathcal{T}}_{n,n}$ is the much-studied <i>Birkhoff-von Neumann polytope</i> of doubly-stochastic matrices. Using a recent asymptotic enumeration of non-negative integer matrices (Canfield and McKay, 2007), we determine the asymptotic volume of ${\mathcal{T}}_{m,n}$ as $n\to \mathrm{\infty }$ with $m=m(n)$ such that $m/n$ neither decreases nor increases too quickly. In particular, we give an asymptotic formula for the volume of ${\mathcal{B}}_n$.

We define the analytic extension of hyperharmonic numbers involving the Pochhammer symbol, gamma and digamma functions. In addition, some sum of hyperharmonic series have been calculated. Surprisingly, the Lerch transcendent appears in the closed form of the sums.

Consider the plane as a checkerboard, with each unit square colored black or white in an arbitrary manner. We show that for any such coloring there are straight line segments, of arbitrarily large length, such that the difference of their white length minus their black length, in absolute value, is at least the square root of their length, up to a multiplicative constant. For the corresponding “finite” problem ($N\times N$ checkerboard) we also prove that we can color it in such a way that the above quantity is at most $C\sqrt{N}\log N$, for any placement of the line segment.

Let $h_R$ denote an $L^{\mathrm{\infty }}$-normalized Haar function adapted to a dyadic rectangle $R\subset [0,1{]}^d$. We show that for all choices of coefficients $\alpha (R)\in \{\pm 1\}$, we have the following lower bound on the $L^{\mathrm{\infty }}$-norms of the sums of such functions, where the sum is over rectangles of a fixed volume:
$$n^{\eta (d)}\lesssim \parallel \sum _{|R|=2^{-n}}\alpha (R)h_R(x){\parallel }_{L^{\mathrm{\infty }}([0,1{]}^d)},\text{for all }\eta (d)<\frac{d-1}{2}+\frac{1}{8d},$$
where the implied constant is independent of $n\ge 1$. The inequality above (without restriction on the coefficients) arises in connection to several areas, such as Probabilities, Approximation, and Discrepancy. With $\eta (d)=(d-1)/2$, the inequality above follows from orthogonality, while it is conjectured that the inequality holds with $\eta (d)=d/2$. This is known and proved in $(Talagrand,1994)$ in the case of $d=2$, and recent papers of the authors $(Bilyk\text{ and }Lacey,2006)$, $(Bilyk\text{ et al., 2007})$ prove that in higher dimensions one can take $\eta (d)>(d-1)/2$, without specifying a particular value of $\eta$. The restriction ${\alpha }_R\in \{\pm 1\}$ allows us to significantly simplify our prior arguments and to find an explicit value of $\eta (d)$.