We show that for \(1\) separated subsets of \(\mathbb{R}^{2}\), the natural Marstrand type slicing statements are false with the counting dimension that was used earlier by Moreira and Lima and variants of which were introduced earlier in different contexts. We construct a \(1\) separated subset \(E\) of the plane which has counting dimension \(1\), while for a positive Lebesgue measure parameter set of tubes of width \(1\), the intersection of the tube with the set \(E\) has counting dimension \(1\). This is in contrast to the behavior of such sets with the mass dimension, in regards to slicing, where the slicing theorems hold true.
A certain residue representation of the inverse binomial coefficients makes them amenable to Egorychev method for the reduction of sums by analytic methods, wherein the main idea is to identify parts of the summands as residues of analytic functions. We illustrate the use of such residue representation on some instances varying in complexity, including a generalization of an identity by Sung Sik U and Kyu Song Chae in [13].
This paper uses exponential sum methods to show that if \(E \subset \mathcal (\mathbb{Z}/p^r)^n \setminus (p)^{(n)}\) has a sufficiently large density and \(j\) is any unit in the finite ring \(\mathbb{Z}/p^r\) then there exist pairs of elements of \(E\) whose dot product equals \(j\). It then applies this to the problem of detecting \(2-\) simplices with endpoints in \(E\).
In this paper, we derive some new combinatorial inequalities by applying well known real analytic results like Hölder’s inequality, Young’s inequality, and Minkowiski’s inequality to the recursively defined sequence \(f_n\) of functions \[\begin{align*} f_0(x) & = \chi_{(-1/2, 1/2)} (x), \nonumber \\ f_{n+1}(x) & = f_n(x+1/2)+ f_n(x-1/2), n \in \mathbb{N}\,\cup \,\{0\}. \end{align*}\] Towards this goal, we derive the closed form of the aforementioned sequence \((f_n)_{n\in \mathbb{N}\,\cup \,\{0\}}\) of functions and show that it is a sequence of simple functions that are linear combinations of characteristic functions of some unit intervals \(I_{n,i},\, i=0,1, …, n\), with values the binomial coefficients \(\binom{n}{i}\) on each unit interval \(I_{n,i}\). We show that \(f_n \in L^p(\mathbb{R})),\, 1\leq p \leq \infty\). Besides applying real analytic methods to formulate some combinatorial inequalities, we also illustrate the application of some combinatorial identities. For example, we use the Vandermonde convolution (or Vandermonde identity), in the study of some properties of the sequence of functions \((f_n)_{n\in\mathbb{ N}\cup \{0\}}\). We show how the \(L^2\) norm of \(f_n\) is related to the Catalan numbers.
We study Lambert series generating functions associated with arithmetic functions \(f\), defined by
$$L_f(q)=\sum_{n\ge1}\frac{f(n)q^n}{1-q^n}=\sum_{m\ge1}(f*1)(m)q^m.$$
These expansions naturally generate divisor sums through Dirichlet convolution with the constant-one function and provide a useful framework for enumerating ordinary generating functions of many multiplicative functions in number theory. This paper presents an overview of key properties of Lambert series, together with combinatorial generalizations and a compendium of formulas for important special cases. The emphasis is on formal and structural aspects of the sequences generated by these series rather than on analytic questions of convergence. In addition to serving as an introduction, the paper provides a consolidated reference for classical identities, recent connections with partition-generating functions, and other useful Lambert series expansions arising in applications.
In this paper, we prove a surprisingly simple formula that counts connected cycle-free families of set partitions, labelled free cacti and coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We also provide a formula that enumerates noncrossing connected, cycle-free pairs of partitions.
We numerically investigate typical graphs in a region of the Strauss model of random graphs with constraints on the densities of edges and triangles. This region, where typical graphs had been expected to be bipodal but turned out to be tripodal, involves edge densities \(e\) below \(e_0 = (3-\sqrt{3})/6 \approx 0.2113\) and triangle densities \(t\) slightly below \(e^3\). We determine the extent of this region in \((e,t)\) space and show that there is a discontinuous phase transition at the boundary between this region and a bipodal phase. We further show that there is at least one phase transition within this region, where the parameters describing typical graphs change discontinuously.
This paper fits in the intersection between two disparate areas of combinatorics. Namely, graph theory and the combinatorics of Catalan words. A Catalan word with n parts is defined as a word w = w1w2⋯wn over the set of positive integers in which w1 = 1 and 1 ≤ wk ≤ wk − 1 + 1 for k = 2, 3, …, n. In order to study the intersection of the two areas, a specific type of graph called a grid graph is defined for each Catalan word. The main thrust of the paper is investigating the degrees of vertices in grid graphs. For each of the possible fixed degrees i ∈ {1, 2, 3, 4}, we find generating functions DFi(x) where the coefficient of xn is the total number of vertices of degree i in all grid graphs with n parts.
This note derives asymptotic upper and lower bounds for the number of planted plane trees on \(n\) nodes assigned labels from the set \(\{1, 2, \dots, k\}\) with the restriction that on any path from the root to a leaf, the labels must strictly decrease. We illustrate an application to calculating the largest eigenvalue of the adjacency matrix of a tree.
Let US be the class of all ultrametric spaces generated by labeled star graphs. We prove that compact US-spaces are the completions of totally bounded ultrametric spaces generated by decreasingly labeled rays. We characterize the ultrametric spaces which are weakly similar to finite US-spaces and describe these spaces by certain four-point conditions.
The Erdős-Anning Theorem states that an integer distance set in the Euclidean plane must have all of its points on a single line or is finite. However, this is not true if we consider area sets. That is, if \((x_1,y_1)\) and \((x_2,y_2)\) are any two vectors contained in the integer lattice, then the area of the parallelogram determined by the two vectors is an integer, showing that the points do not have to lie on a line. We prove a finite field version of these results for \(d=2\) and \(d=3\), showing that if \(E \subset \Bbb{F}_q^d, q=p^2\), where \(p\) is an odd prime and the distance set of \(E\) is \(\Bbb{F}_p\), then the size of \(E\) is at most \(p^d\). Furthermore, we prove that if the area set of \(E\) is a subset of \(\Bbb{F}_p\), then the size of \(E\) is at most \(p^2\) in two dimensions.
Let Fn denote the n-th Fibonacci number defined by Fn = Fn − 1 + Fn − 2 if n ≥ 2, with F0 = 0 and F1 = 1. In this paper, we find determinant identities for several Toeplitz–Hessenberg matrices whose nonzero entries are derived from the sequence kn + m for various fixed m, where kn = Fn − 1. These results may be obtained algebraically as special cases of more general formulas involving the Horadam numbers and the generating functions for the associated sequences of determinants. Equivalent multi-sum identities featuring sums of products of kn terms with multinomial coefficients may be given, which follow from Trudi’s formula. Connections are made to several OEIS entries that have arisen previously in other contexts, perhaps most notably the Padovan number sequence. Finally, we provide combinatorial proofs of our identities involving kn by enumerating (or finding the sum of signs of) various classes of tilings containing squares, dominos, trominos and a special type of tile which can be of arbitrary length.
Integer partitions of \( n \) are viewed as bargraphs (i.e., Ferrers diagrams rotated anticlockwise by 90 degrees) in which the \( i \)-th part of the partition \( x_i \) is given by the \( i \)-th column of the bargraph with \( x_i \) cells. The sun is at infinity in the northwest of our two-dimensional model, and each partition casts a shadow in accordance with the rules of physics. The number of unit squares in this shadow but not being part of the partition is found through a bivariate generating function in \( q \) tracking partition size and \( u \) tracking shadow. To do this, we define triangular \( q \)-binomial coefficients which are analogous to standard \( q \)-binomial coefficients, and we obtain a formula for these. This is used to obtain a generating function for the total number of shaded cells in (weakly decreasing)
partitions of \( n \).
We consider a scalar-valued implicit function of many variables, and provide two closed formulae for all of its partial derivatives. One formula is based on products of partial derivatives of the defining function, the other one involves fewer products of building blocks of multinomial type, and we study the combinatorics of the coefficients showing up in both formulae.
Tensors, or multi-linear forms, are important objects in a variety of areas from analytics, to combinatorics, to computational complexity theory. Notions of tensor rank aim to quantify the “complexity” of these forms, and are thus also important. While there is one single definition of rank that completely captures the complexity of matrices (and thus linear transformations), there is no definitive analog for tensors. Rather, many notions of tensor rank have been defined over the years, each with their own set of uses.
In this paper we survey the popular notions of tensor rank. We give a brief history of their introduction, motivating their existence, and discuss some of their applications in computer science. We also give proof sketches of recent results by Lovett, and Cohen and Moshkovitz, which prove asymptotic equivalence between three key notions of tensor rank over finite fields with at least three elements.
We prove two conjectures due to Sun concerning binomial-harmonic sums. First, we introduce a proof of a formula for Catalan’s constant that had been conjectured by Sun in 2014. Then, using a similar approach as in our first proof, we solve an open problem due to Sun involving the sequence of alternating odd harmonic numbers. Our methods, more broadly, allow us to reduce difficult binomial-harmonic sums to finite combinations of dilogarithms that are evaluable using previously known algorithms.
The aim of this work is to establish congruences \( \pmod{p^2} \) involving the trinomial coefficients \( \binom{np-1}{p-1}_2 \) and \( \binom{np-1}{(p-1)/2}_2 \) arising from the expansion of the powers of the polynomial \( 1 + x + x^2 \). In main results, we extend some known congruences involving the binomial coefficients \( \binom{np-1}{p-1} \) and \( \binom{np-1}{(p-1)/2} \), and establish congruences linking binomial coefficients and harmonic numbers.
In analogy with the semi-Fibonacci partitions studied recently by Andrews, we define semi-\( m \)-Pell compositions. We find that these are in bijection with certain weakly unimodal \( m \)-ary compositions. We give generating functions, bijective proofs, and a number of unexpected congruences for these objects. In the special case of \( m = 2 \), we have a new combinatorial interpretation of the semi-Pell sequence and connections to other objects.
The aim of this paper is to introduce and study a new class of analytic functions which generalize the classes of \(\lambda\)-Spirallike Janowski functions. In particular, we gave the representation theorem, the right side of the covering theorem, starlikeness estimates and some properties related to the functions in the class \( S_\lambda ( T, H, F ) \).
criteria to verify log-convexity of sequences is presented. Iterating this criteria produces infinitely log-convex sequences. As an application, several classical examples of sequences arising in Combinatorics and Special Functions are presented. The paper concludes with a conjecture regarding coefficients of chromatic polynomials.
We discuss the VC-dimension of a class of multiples of integers and primes (equivalently indicator functions) and demonstrate connections to prime counting functions. Additionally, we prove limit theorems for the behavior of an empirical risk minimization rule as well as the weights assigned to the output hypothesis in AdaBoost for these “prime-identifying” indicator functions, when we sample \( mn \) i.i.d. points uniformly from the integers \(\{2, \ldots, n\}\).
Integer compositions and related counting problems are a rich and ubiquitous topic in enumerative combinatorics. In this paper we explore the definition of symmetric and asymmetric peaks and valleys over compositions. In particular, we compute an explicit formula for the generating function for the number of integer compositions according to the number of parts, symmetric, and asymmetric peaks and valleys.
In this paper we show some identities come from the \( q \)-identities of Euler, Jacobi, Gauss, and Rogers-Ramanujan. Some of these identities relate the function sum of divisors of a positive integer \( n \) and the number of integer partitions of \( n \). One of the most intriguing results found here is given by the next equation, for \( n > 0 \),
\[
\sum_{l=1}^n \frac{1}{l!} \sum_{w_1+w_2+\cdots+w_l \in C(n)} \frac{\sigma_1(w_1) \sigma_1(w_2) \cdots \sigma_1(w_l)}{w_1 w_2 \cdots w_l} = p_1(n),
\]
where \( \sigma_1(n) \) is the sum of all positive divisors of \( n \), \( p_1(n) \) is the number of integer partitions of \( n \), and \( C(n) \) is the set of integer compositions of \( n \). In the last section, we show seven applications, one of them is a series expansion for
\[
\frac{(q^{a_1};q^{b_1})_\infty (q^{a_2};q^{b_2})_\infty \cdots (q^{a_k};q^{b_k})_\infty}
{(q^{c_1};q^{d_1})_\infty (q^{c_2};q^{d_2})_\infty \cdots (q^{c_r};q^{d_r})_\infty},
\]
where \( a_1, \ldots, a_k, b_1, \ldots, b_k, c_1, \ldots, c_r, d_1, \ldots, d_r \) are positive integers, and \( |q| < 1 \).
Between Bernoulli/Euler polynomials and Pell/Lucas polynomials, convolution sums are evaluated in closed form via the generating function method. Several interesting identities involving Fibonacci and Lucas numbers are shown as consequences including those due to Byrd \( (1975) \) and Frontczak \( (2020) \).
The notion of length spectrum for natural numbers was introduced by Pong in \([5]\). In this article, we answer the question of how often one can recover a random number from its length spectrum. We also include a quick deduction of a result of LeVeque in \([4]\) on the average order of the size of length spectra.
This paper uses exponential sum methods to show that if \( E \subset M_2(\mathbb{Z}/p^r) \) is a finite set of \( 2 \times 2 \) matrices with sufficiently large density and \( j \) is any unit in the finite ring \( \mathbb{Z}/p^r \), then there exist at least two elements of \( E \) whose difference has determinant \( j \).
In this paper, we introduce a generalized family of numbers and polynomials of one or more variables attached to the formal composition \( f \cdot (g \circ h) \) of generating functions \( f \), \( g \), and \( h \). We give explicit formulae and apply the obtained result to two special families of polynomials; the first concerns the generalization of some polynomials applied to the theory of hyperbolic differential equations recently introduced and studied by \( M. \, Mihoubi \) and \( M. \, Sahari \). The second concerns two-variable Laguerre-based generalized Hermite-Euler polynomials introduced and should be updated to studied recently by \( N. \, U. \, Khan \, \textit{et al.} \).
In this paper, we show that the generalized exponential polynomials and the generalized Fubini polynomials satisfy certain binomial identities and that these identities characterize the mentioned polynomials (up to an affine transformation of the variable) among the class of the normalized Sheffer sequences.
Let \( A \) be a subset of a finite field \( \mathbb{F} \). When \( \mathbb{F} \) has prime order, we show that there is an absolute constant \( c > 0 \) such that, if \( A \) is both sum-free and equal to the set of its multiplicative inverses, then \( |A| < (0.25 – c)|\mathbb{F}| + o(|\mathbb{F}|) \) as \( |\mathbb{F}| \to \infty \). We contrast this with the result that such sets exist with size at least \( 0.25|\mathbb{F}| – o(|\mathbb{F}|) \) when \( \mathbb{F} \) has characteristic 2.
In this paper, we will recover the generating functions of Tribonacci numbers and Chebychev polynomials of first and second kind. By making use of the operator defined in this paper, we give some new generating functions for the binary products of Tribonacci with some remarkable numbers and polynomials. The technique used here is based on the theory of the so-called symmetric functions.
It is shown that if \( V \subseteq \mathbb{F}_p^{n \times \cdots \times n} \) is a subspace of \( d \)-tensors with dimension at least \( tn^{d-1} \), then there is a subspace \( W \subseteq V \) of dimension at least \( t / (dr) – 1 \) whose nonzero elements all have analytic rank \( \Omega_{d, p}(r) \). As an application, we generalize a result of Altman on Szemerédi’s theorem with random differences.
Extensions of a set partition obtained by imposing bounds on the size of the parts and the coloring of some of the elements are examined. Combinatorial properties and the generating functions of some counting sequences associated with these partitions are established. Connections with Riordan arrays are presented.
Every set of natural numbers determines a generating function convergent for \( q \in (-1, 1) \) whose behavior as \( q \to 1^- \) determines a germ. These germs admit a natural partial ordering that can be used to compare sets of natural numbers in a manner that generalizes both cardinality of finite sets and density of infinite sets. For any finite set \( D \) of positive integers, call a set \( S \) “\( D \)-avoiding” if no two elements of \( S \) differ by an element of \( D \). We study the problem of determining, for fixed \( D \), all \( D \)- avoiding sets that are maximal in the germ order. In many cases, we can show that there is exactly one such set. We apply this to the study of one-dimensional packing problems.
We prove some combinatorial identities by an analytic method. We use the property that singular integrals of particular functions include binomial coefficients. In this paper, we prove combinatorial identities from the fact that two results of the particular function calculated as two ways using the residue theorem in the complex function theory are the same. These combinatorial identities are the generalization of a combinatorial identity that has been already obtained
Bargraphs are column convex polyominoes, where the lower edge lies on a horizontal axis. We consider the inner site-perimeter, which is the total number of cells inside the bargraph that have at least one edge in common with an outside cell and obtain the generating function that counts this statistic. From this we find the average inner perimeter and the asymptotic expression for this average as the semi-perimeter tends to infinity. We finally consider those bargraphs where the inner site-perimeter is exactly equal to the area of the bargraph.
Let \( G \) be a graph with \( n \) vertices, then the \( c \)-dominating matrix of \( G \) is the square matrix of order \( n \) whose \( (i, j) \)-entry is equal to 1 if the \( i \)-th and \( j \)-th vertex of \( G \) are adjacent, is also equal to 1 if \( i = j \), \( v_i \in D_c \), and zero otherwise.
The \( c \)-dominating energy of a graph \( G \), is defined as the sum of the absolute values of all eigenvalues of the \( c \)-dominating matrix.
The main purposes of this paper are to introduce the \( c \)-dominating Estrada index of a graph. Moreover, to obtain upper and lower bounds for the \( c \)-dominating Estrada index and investigate the relations between the \( c \)-dominating Estrada in
Let \( G(V,E) \) be a simple connected graph with vertex set \( V \) and edge set \( E \). The Wiener index in the graph is \(W(G) = \sum_{\{u,v\} \subseteq V} d(u,v),\) where \( d(u,v) \) is the distance between \( u \) and \( v \), and the Hosoya polynomial of \( G \) is \(H(G, x) = \sum_{\{u,v\} \subseteq V} x^{d(u,v)}.\) The hyper-Wiener index of \( G \) is \(WW(G) = \frac{1}{2} \left( W(G) + \sum_{\{u,v\} \subseteq V} d^2(u,v) \right).\) In this paper, we compute the Wiener index, Hosoya polynomial, and hyper-Wiener index of Jahangir graph \( J_{8,m} \) for \( m \geq 3 \).
Hybrid numbers are generalization of complex, hyperbolic and dual numbers. In this paper we introduce and study Fibonacci-Pell hybrinomials, i.e. polynomials, which are a generalization of hybrid numbers of the Fibonacci type.
The hub-integrity of a graph is given by the minimum of \( |S| + m(G – S) \), where \( S \) is a hub set and \( m(G – S) \) is the maximum order of the components of \( G – S \). In this paper, the concept of hub edge-integrity is introduced as a new measure of the stability of a graph \( G \), and it is defined as \(HEI(G) = \min\{|S| + m(G – S)\},\) where \( S \) is an edge hub set and \( m(G – S) \) is the order of a maximum component of \( G – S \). Furthermore, an \( HEI \)-set of \( G \) is any set \( S \) for which this minimum is attained. Several properties and bounds on the \( HEI \) are presented, and the relationship between \( HEI \) and other parameters is investigated. The \( HEI \) of some classes of graphs is also computed.
A graph \( G(R) \) is said to be a zero divisor graph of a commutative ring \( R \) with identity if \( x_1, x_2 \in V(G(R)) \) and \( (x_1, x_2) \in E(G(R)) \) if and only if \( x_1 \cdot x_2 = 0 \). The vertex-degree-based eccentric topological indices of zero divisor graphs of commutative rings \( \mathbb{Z}_{p^2} \times \mathbb{Z}_{q^2} \) are studied in this paper, with \( p \) and \( q \) being primes.
The sums \( S(x, t) \) of the centered remainders \( kt – \lfloor kt \rfloor – 1/2 \) over \( k \leq x \) and corresponding Dirichlet series were studied by A. Ostrowski, E. Hecke, H. Behnke, and S. Lang for fixed real irrational numbers \( t \). Their work was originally inspired by Weyl’s equidistribution results modulo 1 for sequences in number theory.
In a series of former papers, we obtained limit functions which describe scaling properties of the Farey sequence of order \( n \) for \( n \to \infty \) in the vicinity of any fixed fraction \( a/b \) and which are independent of \( a/b \). We extend this theory on the sums \( S(x, t) \) and also obtain a scaling behavior with a new limit function. This method leads to a refinement of results given by Ostrowski and Lang and establishes a new proof for the analytic continuation of related Dirichlet series. We will also present explicit relations to the theory of Farey sequences.
Bulgarian solitaire is played on \( n \) cards divided into several piles; a move consists of picking one card from each pile to form a new pile. This can be seen as a process on the set of integer partitions of \( n \): if sorted configurations are represented by Young diagrams, a move in the solitaire consists of picking all cards in the bottom layer of the diagram and inserting the picked cards as a new column. Here we consider a generalization, \( L \)-solitaire, wherein a fixed set of layers \( L \) (that includes the bottom layer) are picked to form a new column.
\( L \)-solitaire has the property that if a stable configuration of \( n \) cards exists it is unique. Moreover, the Young diagram of a configuration is convex if and only if it is a stable (fixpoint) configuration of some \( L \)-solitaire. If the Young diagrams representing card configurations are scaled down to have unit area, the stable configurations corresponding to an infinite sequence of pick-layer sets \( (L_1, L_2, \ldots) \) may tend to a limit shape \( \phi \). We show that every convex \( \phi \) with certain properties can arise as the limit shape of some sequence of \( L_n \). We conjecture that recurrent configurations have the same limit shapes as stable configurations.
For the special case \( L_n = \{1, 1 + \lfloor 1/q_n \rfloor, 1 + \lfloor 2/q_n \rfloor, \ldots\} \), where the pick layers are approximately equidistant with average distance \( 1/q_n \) for some \( q_n \in (0,1] \), these limit shapes are linear (in case \( nq_n^2 \to 0 \)), exponential (in case \( nq_n^2 \to \infty \)), or interpolating between these shapes (in case \( nq_n^2 \to C > 0 \)).
We introduce a polygonal cylinder \( C_{m,n} \), using the Cartesian product of paths \( P_m \) and \( P_n \) and using topological identification of vertices and edges of two opposite sides of \( P_m \times P_n \), and give its Hosoya polynomial, which, depending on odd and even \( m \), is covered in seven separate cases.
In this paper we find recurrence relations for the asymptotic probability a vertex is \(k\) protected in all Motzkin trees. We use a similar technique to calculate the probabilities for balanced vertices of rank \(k\). From this we calculate upper and lower bounds for the probability a vertex is balanced and upper and lower bounds for the expected rank of balanced vertices.
Binomial coefficients of the form \( \binom{\alpha}{\beta} \) for complex numbers \( \alpha \) and \( \beta \) can be defined in terms of the gamma function, or equivalently the generalized factorial function. Less well-known is the fact that if \( n \) is a natural number, the binomial coefficient \( \binom{n}{x} \) can be defined in terms of elementary functions. This enables us to investigate the function \( \binom{n}{x} \) of the real variable \( x \). The results are completely in line with what one would expect after glancing at the graph of \( \binom{3}{x} \), for example, but the techniques involved in the investigation are not the standard methods of calculus. The analysis is complicated by the existence of removable singularities at all of the integer points in the interval \( [0, n] \), and requires multiplying, rearranging, and differentiating infinite series.
In this paper, we analyze the stochastic properties of some large size (area) polyominoes’ perimeter such that the directed column-convex polyomino, the columnconvex polyomino, the directed diagonally-convex polyomino, the staircase (or parallelogram) polyomino, the escalier polyomino, the wall (orbargraph) polyomino. All polyominoes considered here are made of contiguous, not-empty columns, without holes, such that each column must be adjacent to some cell of the previous column. We compute the asymptotic (for large size n) Gaussian distribution of the perimeter, including the corresponding Markov property of the chain of columns, and the convergence to classical Brownian motions of the perimeter seen as a trajectory according to the successive columns. All polyominoes of size n are considered as equiprobable.
Convolution conditions are discussed for the \(q\)-analogue classes of Janowski starlike, convex and spirallike functions.
we discuss a framework for constructing large subsets of \(\mathbb{R}^n\) and \(K^n\) for non-archimedean local fields \(K\). This framework is applied to obtain new estimates for the Hausdorff dimension of angle-avoiding sets and to provide a counterexample to a limiting version of the Capset problem.
Let \( R \) be a commutative ring with unity and \( M \) be an \( R \)-module. The total graph of \( M \) with respect to the singular submodule \( Z(M) \) of \( M \) is an undirected graph \( T(\Gamma(M)) \) with vertex set as \( M \) and any two distinct vertices \( x \) and \( y \) are adjacent if and only if \( x + y \in Z(M) \). In this paper, the author attempts to study the domination in the graph \( T(\Gamma(M)) \) and investigate the domination number and the bondage number of \( T(\Gamma(M)) \) and its induced subgraphs. Some domination parameters of \( T(\Gamma(M)) \) are also studied. It has been shown that \( T(\Gamma(M)) \) is excellent, domatically full, and well covered under certain conditions.
In this paper, we study a class of sequences of polynomials linked to the sequence of Bell polynomials. Some sequences of this class have applications on the theory of hyperbolic differential equations and other sequences generalize Laguerre polynomials and associated Lah polynomials. We discuss, for these polynomials, their explicit expressions, relations to the successive derivatives of a given function, real zeros and recurrence relations. Some known results are significantly simplified.
We show that if \( G \) is a discrete Abelian group and \( A \subseteq G \) has \( \|1_A\|_{B(G)} \leq M \), then \( A \) is \( O(\exp(\pi M)) \)-stable in the sense of Terry and Wolf.
This paper gives some new results on mutually orthogonal graph squares (MOGS). These generalize mutually orthogonal Latin squares in an interesting way. As such, the topic is quite nice and should have broad appeal. MOGS have strong connections to core fields of finite algebra, cryptography, finite geometry, and design of experiments. We are concerned with the Kronecker product of mutually orthogonal graph squares to get new results of the mutually orthogonal certain graphs squares.
For Cauchy numbers of the first kind \(\{a_n\}_{n \geq 0}\) and Cauchy numbers of the second kind \(\{b_n\}_{n \geq 0}\), we prove that two sequences \(\left\{ \sqrt[n]{|a_n|} \right\}_{n \geq 2}\) and \(\left\{ \sqrt[n]{b_n} \right\}_{n \geq 1}\) are log-concave. In addition, we show that two sequences \(\left\{ \frac{1}{\sqrt[n]{|a_n|}} \right\}_{n \geq 2}\) and \(\left\{ \frac{1}{\sqrt[n]{b_n}} \right\}_{n \geq 1}\) are log-balanced.
Let \( p(x) = a_0 + a_1x + \dots + a_nx^n \) be a polynomial with all roots real and satisfying \( x \leq -\delta \) for some \( 0 < \delta < 1 \). We show that for any \( 0 < \epsilon 0 \). As a corollary, we show that if \( m_k(G) \) is the number of matchings with \( k \) edges in a graph \( G \), then for any \( 0 < \epsilon 0 \) is an absolute constant. We prove a similar result for polynomials with complex roots satisfying \( \Re z \leq -\delta \) and apply it to estimate the number of unbranched subgraphs of \( G \).
Let \( G \) be a graph, a subset \( S \subseteq E(G) \) is called an edge hub set of \( G \) if every pair of edges \( e, f \in E(G) \setminus S \) are connected by a path where all internal edges are from \( S \). The minimum cardinality of an edge hub set is called the edge hub number of \( G \), and is denoted by \( h_e(G) \). If \( G \) is a disconnected graph, then any edge hub set must contain all of the edges in all but one of the components, as well as an edge hub set in the remaining component. In this paper, the edge hub number for several classes of graphs is computed, and bounds in terms of other graph parameters are also determined.
In 1998, D. Callan obtained a binomial identity involving the derangement numbers. In this paper, by using the theory of formal series, we extend such an identity to the generalized derangement numbers. Then, by using the same technique, we obtain other identities of the same kind for the generalized arrangement numbers, the generalized Laguerre polynomials, the generalized Hermite polynomials, the generalized exponential polynomials and the generalized Bell numbers, the hyperharmonic numbers, the Lagrange polynomials and the Gegenbauer polynomials.
In this paper, we present a method to construct a cyclic orthogonal double cover (CODC) of circulant graphs by certain kinds of coronas that model by linear functions.
Following the work of Cano and Díaz, we study continuous binomial coefficients and Catalan numbers. We explore their analytic properties, including integral identities and generalizations of discrete convolutions. We also conduct an in-depth analysis of a continuous analogue of the binomial distribution, including a stochastic representation as a Goldstein-Kac process.
In this paper, we introduce a new operator in order to derive some properties of homogeneous symmetric functions. By making use of the proposed operator, we give some new generating functions for \( k \)-Fibonacci numbers, \( k \)-Pell numbers, and the product of sequences and Chebyshev polynomials of the second kind.
In this paper, we introduce the concept block matrix (B-matrix) of a graph \( G \), and obtain some coefficients of the characteristic polynomial \( \phi(G, \mu) \) of the B-matrix of \( G \). The block energy \( E_B(G) \) is established. Further upper and lower bounds for \( E_B(G) \) are obtained. In addition, we define a uni-block graph. Some properties and new bounds for the block energy of the uni-block graph are presented.
We consider analogs of several classical diophantine equations, such as Fermat’s last theorem and Catalan’s conjecture, for certain classes of analytic functions. We give simple direct proofs avoiding use of deep theorems in complex analysis. As a byproduct of our results, we obtain new proofs for the corresponding results over polynomials.
Applying the multisection series method to the MacLaurin series expansion of arcsin-function, we transform the Apéry–like series involving the central binomial coefficients into systems of linear equations. By resolving the linear systems (for example, by Mathematica), we establish numerous remarkable infinite series formulae for π and logarithm functions, including several recent results due to Almkvist et al. (2003) and Zheng (2008).
We introduce the notion of capacity (ability to contain water) for compositions. Initially the compositions are defined on a finite alphabet \([k]\) and thereafter on \(\mathbb{N}\). We find a capacity generating function for all compositions, the average capacity generating function and an asymptotic expression for the average capacity as the size of the composition increases to infinity
As suggested by Currie, we apply the probabilistic method to problems regarding pattern avoidance. Using techniques from analytic combinatorics, we calculate asymptotic mean pattern occurrence and use them in conjunction with the probabilistic method to establish new results about the Ramsey theory of unavoidable patterns in the abelian full word case and in the nonabelian partial word case.
In this paper, we present several explicit formulas of the sums and hypersums of the powers of the first \((n + 1)\)-terms of a general arithmetic sequence in terms of Stirling numbers and generalized Bernoulli polynomials
We define a generalized class of modified zeta series transformations generating the partial sums of the Hurwitz zeta function and series expansions of the Lerch transcendent function. The new transformation coefficients we define within the article satisfy expansions by generalized harmonic number sequences as the partial sums of the Hurwitz zeta function. These transformation coefficients satisfy many properties which are analogous to known identities and expansions of the Stirling numbers of the first kind and to the known transformation coefficients employed to enumerate variants of the polylogarithm function series. Applications of the new results we prove in the article include new series expansions of the Dirichlet beta function, the Legendre chi function, BBP-type series identities for special constants, alternating and exotic Euler sum variants, alternating zeta functions with powers of quadratic denominators, and particular series defining special cases of the Riemann zeta function constants at the positive integers s ≥ 3.
Let \([k] = \{1, 2, \ldots, k\}\) be an alphabet over \(k\) letters. A word \(\omega\) of length \(n\) over alphabet \([k]\) is an element of \([k]^n\) and is also called \(k\)-ary word of length \(n\). We say that \(\omega\) contains a peak, if exists \(2 \leq i \leq n-1\) such that \(\omega_{i-1} \omega_{i+1}\). We say that \(\omega\) contains a symmetric peak, if exists \(2 \leq i \leq n-1\) such that \(\omega_{i-1} = \omega_{i+1} < \omega_i\), and contains a non-symmetric peak, otherwise. In this paper, we find an explicit formula for the generating functions for the number of \(k\)-ary words of length \(n\) according to the number of symmetric peaks and non-symmetric peaks in terms of Chebyshev polynomials of the second kind. Moreover, we find the number of symmetric and non-symmetric peaks in \(k\)-ary word of length \(n\) in two ways by using generating functions techniques, and by applying probabilistic methods.
In this paper, we first give a new \( q \)-analogue of the Lah numbers. Then we show the irreducible factors of the \( q \)-Lah numbers over \( \mathbb{Z} \).
Let \( A \) and \( B \) be additive sets of \( \mathbb{Z}_{2k} \), where \( A \) has cardinality \( k \) and \( B = v \cdot C A \) with \( v \in \mathbb{Z}_{2k}^\times \). In this note, some bounds for the cardinality of \( A + B \) are obtained using four different approaches. We also prove that in a special case, the bound is not sharp and we can recover the whole group as a sumset.
In this paper, we analyze the asymptotic number \( I(m,n) \) of involutions of large size \( n \) with \( m \) singletons. We consider a central region and a non-central region. In the range \( m = n – n^\alpha \), \( 0 < \alpha < 1 \), we analyze the dependence of \( I(m,n) \) on \( \alpha \). This paper fits within the framework of Analytic Combinatorics.
An inverse-conjugate composition of a positive integer \(m\) is an ordered partition of \(m\) whose conjugate coincides with its reversal. In this paper, we consider inverse-conjugate compositions in which the part sizes do not exceed a given integer \(k\). It is proved that the number of such inverse-conjugate compositions of \(2n – 1\) is equal to \(2F_n^{(k-1)}\), where \(F_n^{(k)}\) is a Fibonacci \(k\)-step number. We also give several connections with other types of compositions, and obtain some analogues of classical combinatorial identities.
S. Ekhad and D. Zeilberger recently proved that the multivariate generating function for the number of simple singular vector tuples of a generic \(m_1 \times · · · \times m_d\) tensor has an elegant rational form involving elementary symmetric functions, and provided a partial conjecture for the asymptotic behavior of the cubical case \(m_1 = · · · = m_d\). We prove this conjecture and further identify completely the dominant asymptotic term, including the multiplicative constant. Finally, we use the method of differential approximants to conjecture that the subdominant connective constant effect observed by Ekhad and Zeilberger for a particular case in fact occurs more generally
In this paper, we define the q-analogue of the so-called symmetric infinite matrix algorithm. We find an explicit formula for entries in the associated matrix and also for the generating function of the k-th row of this matrix for each fixed k. This helps us to derive analytic and number theoretic identities with respect to the q-harmonic numbers and q-hyperharmonic numbers of Mansour and Shattuck.
Bargraphs are lattice paths in \(\mathbb{N}_0^2\) with three allowed types of steps: up \((0,1)\), down \((0,-1)\), and horizontal \((1,0)\). They start at the origin with an up step and terminate immediately upon return to the \(x\)-axis. A wall of size \(r\) is a maximal sequence of \(r\) adjacent up steps. In this paper, we develop the generating function for the total number of walls of fixed size \(r \geq 1\). We then derive asymptotic estimates for the mean number of such walls.
We survey four instances of the Fourier analytic ‘transference principle’or ‘dense model lemma’, which allows one to approximate an unbounded function on the integers by a bounded function with similar Fourier transform. Such a result forms a component of a general method pioneered by Green to count solutions to a single linear equation in a sparse subset of integers.
Let \( E \subseteq \mathbb{F}_q^2 \) be a set in the 2-dimensional vector space over a finite field with \( q \) elements, which satisfies \(|E| > q\). There exist \( x, y \in E \) such that \(|E \cdot (y – x)| > q/2\). In particular, \( (E + E) \cdot (E – E) = \mathbb{F}_q.\)
Let \((x(n))_{n \geq 1}\) be an \(s\)-dimensional Niederreiter-Xing sequence in base \(b\). Let \(D((x(n))_{n=1}^N)\) be the discrepancy of the sequence \((x(n))_{n=1}^N\). It is known that \(ND((x(n))_{n=1}^N) = O(\ln^s N)\) as \(N \to \infty\). In this paper, we prove that this estimate is exact. Namely, there exists a constant \(K > 0\), such that
\[
\inf_{w \in [0,1]^s} \sup_{1 \leq N \leq b^m} ND((x(n) \oplus w)_{n=1}^N) \geq K \ln^s \quad \text{ for } m = 1, 2, \ldots.
\]
We also get similar results for other explicit constructions of \((t,s)\)-sequences.
We define a new class of generating function transformations related to polylogarithm functions, Dirichlet series, and Euler sums. These transformations are given by an infinite sum over the jth derivatives of a sequence generating function and sets of generalized coefficients satisfying a non-triangular recurrence relation in two variables. The generalized transformation coefficients share a number of analogous properties with the Stirling numbers of the second kind and the known harmonic number expansions of the unsigned Stirling numbers of the first kind.
We prove a number of properties of the generalized coefficients which lead to new recurrence relations and summation identities for the k-order harmonic number sequences. Other applications of the generating function transformations we define in the article include new series expansions for the polylogarithm function, the alternating zeta function, and the Fourier series for the periodic Bernoulli polynomials. We conclude the article with a discussion of several specific new “almost” linear recurrence relations between the integer-order harmonic numbers and the generalized transformation coefficients, which provide new applications to studying the limiting behavior of the zeta function constants, ζ(k), at integers k ≥ 2.
Generating functions for Pell and Pell-Lucas numbers are obtained. Applications are given for some results recently obtained by Mansour [Mansour12]; by using an alternative approach that considers the action of the operator \(\delta_{e_1 e_2}^k\) to the series \(\sum_{j=0}^\infty a_j (e_1 z)^j\).
Motivated by the Monthly problem #11515, we prove further interesting formulae for trigonometric series by means of telescoping method.
The main theorem establishes the generating function \(F\) which counts the number of times the staircase \(1 + 2 + 3 + \cdots + m^+\) fits inside an integer composition of \(n\).
\[
F = \frac{k_m – \frac{q x^m y}{1-x} k_{m-1}}{(1-q)x^{\binom{m+1}{2}} \left( \frac{y}{1-x} \right)^m + \frac{1-x-xy}{1-x} \left( k_m – \frac{q x^m y}{1-x} k_{m-1} \right)}.
\]
where
\[
k_m = \sum_{j=0}^{m-1} x^{mj – \binom{j}{2}} \left( \frac{y}{1-x} \right)^j.
\]
Here \(x\) and \(y\) respectively track the composition size and number of parts, whilst \(q\) tracks the number of such staircases contained.
An involution is a permutation that is its own inverse. Given a permutation \(\sigma\) of \([n]\), let \(N_n(\sigma)\) denote the number of ways to write \(\sigma\) as a product of two involutions of \([n]\). If we endow the symmetric groups \(S_n\) with uniform probability measures, then the random variables \(N_n\) are asymptotically lognormal.
The proof is based upon the observation that, for most permutations \(\sigma\), \(N_n(\sigma)\) can be well-approximated by \(B_n(\sigma)\), the product of the cycle lengths of \(\sigma\). Asymptotic lognormality of \(N_n\) can therefore be deduced from Erdős and Turán’s theorem that \(B_n\) is itself asymptotically lognormal.
The Stirling number of the second kind \( S(n, k) \) counts the number of ways to partition a set of \( n \) labeled balls into \( k \) non-empty unlabeled cells. We extend this problem and give a new statement of the \( r \)-Stirling numbers of the second kind and \( r \)-Bell numbers. We also introduce the \( r \)-mixed Stirling number of the second kind and \( r \)-mixed Bell numbers. As an application of our results we obtain a formula for the number of ways to write an integer \( m > 0 \) in the form \( m_1 \cdot m_2 \cdot \cdots \cdot m_k \), where \( k \geq 1 \) and \( m_i \)’s are positive integers greater than 1.
Packing patterns in permutations concerns finding the permutation with the maximum number of a prescribed pattern. In 2002, Albert, Atkinson, Handley, Holton and Stromquist showed that there always exists a layered permutation containing the maximum number of a layered pattern among all permutations of length n. Consequently the packing density for all but two (up to equivalence) patterns up to length 4 can be obtained. In this note we consider the analogous question for colored patterns and permutations. By introducing the concept of “colored blocks” we characterize the optimal permutations with the maximum number of a given colored pattern when it contains at most three colored blocks. As examples we apply this characterization to find the optimal permutations of various colored patterns and subsequently obtain their corresponding packing densities.
We extend the main result of the paper “Arithmetic progressions in sets of fractional dimension” ([12]) in two ways. Recall that in [12], Łaba and Pramanik proved that any measure \( \mu \) with Hausdorff dimension \( \alpha \in (1 – \epsilon_0, 1) \) (here \( \epsilon_0 \) is a small constant) large enough depending on its Fourier dimension \( \beta \in (2/3, \alpha] \) contains in its support three-term arithmetic progressions (3APs). In the present paper, we adapt an approach introduced by Green in “Roth’s Theorem in the Primes” to both lower the requirement on \( \beta \) to \( \beta > 1/2 \) (and \( \epsilon_0 \) to \( 1/10 \)) and perhaps more interestingly, extend the result to show for any \( \delta > 0 \), if \( \alpha \) is large enough depending on \( \delta \), then \( \mu \) gives positive measure to the (basepoints of the) non-trivial 3APs contained within any set \( A \) for which \( \mu(A) > \delta \).
Let \( f(x) = 1 + \sum_{n=1}^\infty a_n x^n \) be a formal power series with complex coefficients. Let \( \{r_n\}_{n=1}^\infty \) be a sequence of nonzero integers. The Integer Power Product Expansion of \( f(x) \), denoted ZPPE, is \( \prod_{k=1}^\infty (1 + w_k x^k)^{r_k} \). Integer Power Product Expansions enumerate partitions of multi-sets. The coefficients \( \{w_k\}_{k=1}^\infty \) themselves possess interesting algebraic structure. This algebraic structure provides a lower bound for the radius of convergence of the ZPPE and provides an asymptotic bound for the weights associated with the multi-sets.
We give an arithmetic version of the recent proof of the triangle removal lemma by Fox [Fox11], for the group \( \mathbb{F}_2^n \). A triangle in \( \mathbb{F}_2^n \) is a triple \( (x, y, z) \) such that \( x + y + z = 0 \). The triangle removal lemma for \( \mathbb{F}_2^n \) states that for every \( \varepsilon > 0 \) there is a \( \delta > 0 \), such that if a subset \( A \) of \( \mathbb{F}_2^n \) requires the removal of at least \( \varepsilon \cdot 2^n \) elements to make it triangle-free, then it must contain at least \( \delta \cdot 2^{2n} \) triangles.
This problem was first studied by Green [Gre05] who proved a lower bound on \( \delta \) using an arithmetic regularity lemma. Regularity-based lower bounds for triangle removal in graphs were recently improved by Fox, and we give a direct proof of an analogous improvement for triangle removal in \( \mathbb{F}_2^n \).
The improved lower bound was already known to follow (for triangle-removal in all groups) using Fox’s removal lemma for directed cycles and a reduction by Král, Serra, and Vena~\cite{KSV09} (see [Fox11, CF13]). The purpose of this note is to provide a direct Fourier-analytic proof for the group \( \mathbb{F}_2^n \).
A set of natural numbers tiles the plane if a square-tiling of the plane exists using exactly one square of side length n for every n in the set. In [9] it is shown that N, the set of all natural numbers, tiles the plane. We answer here a number of questions from that paper. We show that there is a simple tiling of the plane (no nontrivial subset of squares forms a rectangle). We show that neither the odd numbers nor the prime numbers tile the plane. We show that N can tile many, even infinitely many planes.
Let \( s, t \) be any numbers in \( \{0,1\} \) and let \( \pi = \pi_1 \pi_2 \cdots \pi_m \) be any word. We say that \( i \in [m-1] \) is an \( (s,t) \)-parity-rise if \( \pi_i \equiv s \pmod{2} \), \( \pi_{i+1} \equiv t \pmod{2} \), and \( \pi_i < \pi_{i+1} \). We denote the number of occurrences of \( (s,t) \)-parity-rises in \( \pi \) by \( \text{rise}_{s,t}(\pi) \). Also, we denote the total sizes of the \( (s,t) \)-parity-rises in \( \pi \) by \( \text{size}_{s,t}(\pi) \), that is, \( \text{size}_{s,t}(\pi) = \sum_{\pi_i < \pi_{i+1}} (\pi_{i+1} – \pi_i). \) A composition \( \pi = \pi_1 \pi_2 \cdots \pi_m \) of a positive integer \( n \) is an ordered collection of one or more positive integers whose sum is \( n \). The number of summands, namely \( m \), is called the number of parts of \( \pi \). In this paper, by using tools of linear algebra, we found the generating function that counts the number of all compositions of \( n \) with \( m \) parts according to the statistics \( \text{rise}_{s,t} \) and \( \text{size}_{s,t} \), for all \( s, t \).
In the paper, utilizing respectively the induction, a generating function of the Lah numbers, the Chu-Vandermonde summation formula, an inversion formula, the Gauss hypergeometric series, and two generating functions of Stirling numbers of the first kind, the authors collect and provide six proofs for an identity of the Lah numbers.
We prove that if \( A \subset \mathbb{Z}_q \setminus \{0\} \), \( A \neq \langle p \rangle \), \( q = p^\ell \), \( \ell \geq 2 \) with \( |A| > C \sqrt[3]{\sqrt{\ell}^2 q^{(1-\frac{1}{4\ell})}} \), then
\[
|P(A) \cdot P(A)| \geq C’ q^3
\]
where
\[
P(A) = \left\{ \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \in SL_2(\mathbb{Z}_q) : a_{11} \in A \cap \mathbb{Z}_q^\times, a_{12}, a_{21} \in A \right\}.
\]
The proof relies on a result in \([4]\) previously established by D. Covert, A. Iosevich, and J. Pakianathan, which implies that if \( |A| \) is much larger than \( \sqrt{\ell} q^{(1-\frac{1}{4\ell})} \), then
\[
|\{(a_{11}, a_{12}, a_{21}, a_{22}) \in A \times A \times A \times A : a_{11} a_{22} + a_{12} a_{21} = t\}| = |A|^4 q^{-1} + \mathcal{R}(t)
\]
where \( |\mathcal{R}(t)| \leq \ell |A|^2 q^{(1-\frac{1}{2\ell})} \).
By extending former results of Ehrhart, it was shown by Peter McMullen that the number of lattice points in the Minkowski-sum of dilated rational polytopes is a quasipolynomial function in the dilation factors. Here we take a closer look at the coefficients of these quasi-polynomials and show that they are piecewise polynomials themselves and that they are related to each other by a simple differential equation. As a corollary, we obtain a refinement of former results on lattice points in vector dilated polytopes
Using the Saddle point method and multiseries expansions, we obtain from the generating function of the Eulerian numbers \( A_{n,k} \) and Cauchy’s integral formula, asymptotic results in non-central region. In the region \( k = n – n^\alpha \), \( 1 > \alpha > 1/2 \), we analyze the dependence of \( A_{n,k} \) on \(\alpha\). This paper fits within the framework of Analytic Combinatorics.
We introduce the problem of isolating several nodes in random recursive trees by successively removing random edges, and study the number of random cuts that are necessary for the isolation. In particular, we analyze the number of random cuts required to isolate \(\ell\) selected nodes in a size-\(n\) random recursive tree for three different selection rules, namely (i) isolating all of the nodes labelled \(1, 2, \ldots, \ell\) (thus nodes located close to the root of the tree), (ii) isolating all of the nodes labelled \(n + 1 – \ell, n + 2 – \ell, \ldots, n\) (thus nodes located at the fringe of the tree), and (iii) isolating \(\ell\) nodes in the tree, which are selected at random before starting the edge-removal procedure. Using a generating functions approach we determine for these selection rules the limiting distribution behaviour of the number of cuts to isolate all selected nodes, for \(\ell\) fixed and \(n \to \infty\).
Guibert and Linusson introduced the family of doubly alternating Baxter permutations, i.e., Baxter permutations \( \sigma \in S_n \), such that \( \sigma \) and \( \sigma^{-1} \) are alternating. They proved that the number of such permutations in \( S_{2n} \) and \( S_{2n+1} \) is the Catalan number \( C_n \). In this paper, we compute the expected limit shape of such permutations, following the approach by Miner and Pak.
In his celebrated proof of Szemerédi’s theorem that a set of integers of positive density contains arbitrarily long arithmetic progressions, W. T. Gowers introduced a certain sequence of norms \( \|\cdot\|_{U^2[\mathbb{N}]} \leq \|\cdot\|_{U^3[\mathbb{N}]} \leq \cdots \) on the space of complex-valued functions on the set \( [N] \). An important question regarding these norms concerns for which functions they are `large’ in a certain sense.
This question has been answered fairly completely by B. Green, T. Tao and T. Ziegler in terms of certain algebraic functions called \textit{nilsequences}. In this work, we show that more explicit functions called \textit{bracket polynomials} have `large’ Gowers norm. Specifically, for a fairly large class of bracket polynomials, called \textit{constant-free bracket polynomials}, we show that if \( \phi \) is a bracket polynomial of degree \( k-1 \) on \( [N] \), then the function \( f : n \mapsto e(\phi(n)) \) has Gowers \( U^k[\mathbb{N}] \)-norm uniformly bounded away from zero.
We establish this result by first reducing it to a certain recurrence property of sets of constant-free bracket polynomials. Specifically, we show that if \( \theta_1, \ldots, \theta_r \) are constant-free bracket polynomials, then their values, modulo 1, are all close to zero on at least some constant proportion of the points \( 1, \ldots, N \).
The proof of this statement relies on two deep results from the literature. The first is work of V. Bergelson and A. Leibman showing that an arbitrary bracket polynomial can be expressed in terms of a so-called \textit{polynomial sequence} on a nilmanifold. The second is a theorem of B. Green and T. Tao describing the quantitative distribution properties of such polynomial sequences.
In the special cases of the bracket polynomials \( \phi_{k-1}(n) = \alpha_{k-1} n^{k-2} \{ \alpha_1 n \cdots \} \) with \( k \leq 5 \), we give elementary alternative proofs of the fact that \( \|\phi_{k-1}\|_{U^k[\mathbb{N}]} \) is `large,’ without reference to nilmanifolds. Here we write \( \{x\} \) for the fractional part of \( x \), chosen to lie in \( (-1/2, 1/2] \).
The theory of generic smooth closed plane curves initiated by Vladimir Arnold is a beautiful fusion of topology, combinatorics, and analysis. The theory remains fairly undeveloped. We review existing methods to describe generic smooth closed plane curves combinatorially, introduce a new one, and give an algorithm for efficient computation of Arnold’s invariants. Our results provide a good source of future research projects that involve computer experiments with plane curves. The reader is not required to have background in topology and even undergraduate students with basic knowledge of differential geometry and graph theory will easily understand our paper.
A level (\(L\)) is an occurrence of two consecutive equal entries in a word \(w = w_1 w_2 \cdots\), while a rise (\(R\)) or descent (\(D\)) occurs when the right or left entry, respectively, is strictly larger. If \(u = u_1 u_2 \cdots u_n\) and \(v = v_1 v_2 \cdots v_n\) are \(k\)-ary words of the same given length and \(1 \leq i \leq n-1\), then there is, for example, an occurrence of \(LR\) at index \(i\) if \(u_i = u_{i+1}\) and \(v_i < v_{i+1}\), and likewise for the other possibilities. Similar terminology may be used when discussing ordered \(d\)-tuples of \(k\)-ary words of length \(n\) (the set of which we’ll often denote by \([k]^{nd}\)).
In this paper, we consider the problem of enumerating the members of \([k]^{nd}\) according to the number of occurrences of the pattern \(\rho\), where \(d \geq 1\) and \(\rho\) is any word of length \(d\) in the alphabet \(\{L, R, D\}\). In particular, we find an explicit formula for the generating function counting the members of \([k]^{nd}\) according to the number of occurrences of the patterns \(\rho = L^i R^{d-i}\), \(0 \leq i \leq d\), which, by symmetry, is seen to solve the aforementioned problem in its entirety. We also provide simple formulas for the average number of occurrences of \(\rho\) within all the members of \([k]^{nd}\), providing both algebraic and combinatorial proofs. Finally, in the case \(d = 2\), we solve the problem above where we also allow for \textit{weak rises} (which we’ll denote by \(R_w\)), i.e., indices \(i\) such that \(w_i \leq w_{i+1}\) in \(w\). Enumerating the cases \(R_w R_w\) and \(R_w R_{uw}\) seems to be more difficult, and to do so, we combine the kernel method with the simultaneous use of several recurrences.
Let \( G \) be a simple, connected graph with finite vertex set \( V \) and edge set \( E \). A depletion of \( G \) is a permutation \( v_1 v_2 \dots v_n \) of the elements of \( V \) with the property that \( v_i \) is adjacent to some member of \( \{v_1, v_2, \dots, v_{i-1}\} \) for each \( i \geq 2 \). Depletions model the spread of a rumor or a disease through a population and are related to heaps. In this paper, we develop techniques for enumerating the depletions of a graph.
This statistic, i.e. the sum of positions of records, has been the object of recent interest in the literature. Using the saddle point method, we obtain from the generating function of the sum of positions of records in random permutations and Cauchy’s integral formula, asymptotic results in central and non-central regions. In the non-central region, we derive asymptotic expansions generalizing some results by Kortchemski. In the central region, we obtain a limiting distribution related to Dickman’s function. This paper fits within the framework of Analytic Combinatorics.
We exhibit proofs of Furstenberg’s Multiple Recurrence Theorem and of a special case of Furstenberg and Katznelson’s multidimensional version of this theorem, using an analog of the density-increment argument of Roth and Gowers. The second of these results requires also an analog of some recent finitary work by Shkredov.
Many proofs of these multiple recurrence theorems are already known. However, the approach of this paper sheds some further light on the well-known heuristic correspondence between the ergodic-theoretic and combinatorial aspects of multiple recurrence and Szemeredi’s Theorem. Focusing on the density- increment strategy highlights several close points of connection between these settings.
We study the Euler–Frobenius numbers, a generalization of the Eulerian numbers, and the probability distribution obtained by normalizing them. This distribution can be obtained by rounding a sum of independent uniform random variables; this is more or less implicit in various results and we try to explain this and various connections to other areas of mathematics, such as spline theory.
The mean, variance and (some) higher cumulants of the distribution are calculated. Asymptotic results are given. We include a couple of applications to rounding errors and election methods.
An important problem in analytic and geometric combinatorics is estimating the number of lattice points in a compact convex set in a Euclidean space. Such estimates have numerous applications throughout mathematics. In this note, we exhibit applications of a particular estimate of this sort to several counting problems in number theory: counting integral points and units of bounded height over number fields, counting points of bounded height over positive definite quaternion algebras, and counting points of bounded height with a fixed support over global function fields. Our arguments use a collection of height comparison inequalities for heights over a number field and over a quaternion algebra. We also show how these inequalities can be used to obtain existence results for points of bounded height over a quaternion algebra, which constitute non-commutative analogues of variations of the classical Siegel’s lemma and Cassels’ theorem on small zeros of quadratic forms.
We prove that when a pre-independence space satisfies some natural properties, then its cyclic flats form a bounded lattice under set inclusion. Additionally, we show that a bounded lattice is isomorphic to the lattice of cyclic flats of a pre-independence space. We also prove that the notion of cyclic width gives rise to dual-closed and minorclosed classes of B-matroids. Finally, we find a difference between finite matroids and B-matroids by using the notion of well-quasi-ordering.
In this paper, we generalize an earlier statistic on square-and-domino tilings by considering only those squares covering a multiple of k, where k is a fixed positive integer. We consider the distribution of this statistic jointly with the one that records the number of dominos in a tiling. We derive both finite and infinite sum expressions for the corresponding joint distribution polynomials, the first of which reduces when k = 1 to a prior result. The cases q = 0 and q = −1 are noted for general k. Finally, the case k = 2 is considered specifically, where further results may be given, including a combinatorial proof when q = −1.
A sequence of coefficients appearing in a recurrence for the Narayana polynomials is generalized. The coefficients are given a probabilistic interpretation in terms of beta distributed random variables. The recurrence established by M. Lasalle is then obtained from a classical convolution identity. Some arithmetical properties of the generalized coefficients are also established.
We consider the problem of packing fixed-length patterns into a permutation, and develop a connection between the number of large patterns and the number of bonds in a permutation. Improving upon a result of Kaplansky and Wolfowitz, we obtain exact values for the expectation and variance for the number of large patterns in a random permutation. Finally, we are able to generalize the idea of bonds to obtain results on fixed-length patterns of any size, and present a construction that maximizes the number of patterns of a fixed size.
We present in this work results on some distributions of permutation statistics of random elements of the wreath product \( G_{r,n} = C_r \wr S_n \). We consider the distribution of the descent number, the flag major index, the excedance, and the number of fixed points, over the whole group \( G_{r,n} \), or over the subclasses of derangements and involutions. We compute the mean, variance and moment generating function, and establish the asymptotic distributions of these statistics.
Let \( A \) be a subset of \( \mathbb{F}_p^n \), the \( n \)-dimensional linear space over the prime field \( \mathbb{F}_p \), of size at least \( \delta N \) (\( N = p^n \)), and let \( S_v = P^{-1}(v) \) be the level set of a homogeneous polynomial map \( P : \mathbb{F}_p^n \to \mathbb{F}_p^R \) of degree \( d \), for \( v \in \mathbb{F}_p^R \). We show that, under appropriate conditions, the set \( A \) contains at least \( c N|S| \) arithmetic progressions of length \( l \leq d \) with common difference in \( S_v \), where \( c \) is a positive constant depending on \( \delta \), \( l \), and \( P \). We also show that the conditions are generic for a class of sparse algebraic sets of density \( \approx N^{-\gamma} \).
In this paper, we investigate properties of a new class of generalized Cauchy numbers. By using the method of coecient, we establish a series of identities involving generalized Cauchy numbers, which generalize some results for the Cauchy numbers. Furthermore, we give some asymptotic approximations of certain sums related to the generalized Cauchy numbers.
Let \( F(x) = \sum_{\nu \in \mathbb{N}^d} F_\nu x^\nu \) be a multivariate power series with complex coefficients that converges in a neighborhood of the origin. Assume \( F = G / H \) for some functions \( G \) and \( H \) holomorphic in a neighborhood of the origin. We derive asymptotics for the coefficients \( F_{r\alpha} \) as \( r \to \infty \) with \( r\alpha \in \mathbb{N}^d \) for \( \alpha \) in a permissible subset of \( d \)-tuples of positive reals. More specifically, we give an algorithm for computing arbitrary terms of the asymptotic expansion for \( F_{r\alpha} \) when the asymptotics are controlled by a transverse multiple point of the analytic variety \( H = 0 \). This improves upon earlier work by R. Pemantle and M. C. Wilson. We have implemented our algorithm in Sage and apply it to obtain accurate numerical results for several rational combinatorial generating functions.
Let \( P(n, k) \) denote the set of partitions of \( [n] = \{1, 2, \ldots, n\} \) containing exactly \( k \) blocks. Given a partition \( \Pi = B_1 / B_2 / \cdots / B_k \in P(n, k) \) in which the blocks are listed in increasing order of their least elements, let \( \pi = \pi_1 \pi_2 \cdots \pi_n \) denote the canonical sequential form wherein \( j \in B_{\pi_j} \) for all \( j \in [n] \). In this paper, we supply an explicit formula for the generating function which counts the elements of \( P(n, k) \) according to the number of strings \( k1 \) and \( r(r+1) \), taken jointly, occurring in the corresponding canonical sequential forms. A comparable formula for the statistics on \( P(n, k) \) recording the number of strings \( 1k \) and \( r(r-1) \) is also given, which may be extended to strings \( r(r-1) \cdots (r-m) \) of arbitrary length using linear algebra. In addition, we supply algebraic and combinatorial proofs of explicit formulas for the total number of occurrences of \( k1 \) and \( r(r+1) \) within all the members of \( P(n, k) \).
A word is centrosymmetric if it is invariant under the reverse-complement map. In this paper, we give enumerative results on k-ary centrosymmetric words of length n avoiding a pattern of length 3 with no repeated letters.
We consider a bivariate rational generating function
\[
F(x, y) = \frac{P(x, y)}{Q(x, y)} = \sum_{r, s \geq 0} a_{r,s} x^r y^s
\]
under the assumption that the complex algebraic curve \( \mathcal{V} \) on which \( Q \) vanishes is smooth. Formulae for the asymptotics of the coefficients \( \{a_{r,s}\} \) are derived in [PW02]. These formulae are in terms of algebraic and topological invariants of \( \mathcal{V} \), but up to now these invariants could be computed only under a minimality hypothesis, namely that the dominant saddle must lie on the boundary of the domain of convergence. In the present paper, we give an effective method for computing the topological invariants, and hence the asymptotics of {\(a_{rs}\)}, without the minimality assumption. This leads to a theoretically rigorous algorithm, whose implementation is in progress at http://www.mathemagix.org
This paper presents a new construction of the \( m \)-fold metaplectic cover of \( \mathrm{GL}_n \) over an algebraic number field \( k \), where \( k \) contains a primitive \( m \)-th root of unity. A 2-cocycle on \( \mathrm{GL}_n(\mathbb{A}) \) representing this extension is given, and the splitting of the cocycle on \( \mathrm{GL}_n(k) \) is found explicitly. The cocycle is smooth at almost all places of \( k \). As a consequence, a formula for the Kubota symbol on \( \mathrm{SL}_n \) is obtained. The construction of the paper requires neither class field theory nor algebraic \( K \)-theory but relies instead on naive techniques from the geometry of numbers introduced by W. Habicht and T. Kubota. The power reciprocity law for a number field is obtained as a corollary.
Let \( \pi = \pi_1 \pi_2 \cdots \pi_n \) be any permutation of length \( n \), we say a descent \( \pi_i \pi_{i+1} \) is a {lower}, {middle}, {upper} if there exists \( j > i+1 \) such that \( \pi_j < \pi_{i+1}, \pi_{i+1} < \pi_j < \pi_i, \pi_i < \pi_j \), respectively. Similarly, we say a rise \( \pi_i \pi_{i+1} \) is a {lower}, {middle}, {upper} if there exists \( j > i+1 \) such that \( \pi_j < \pi_i, \pi_i < \pi_j < \pi_{i+1}, \pi_{i+1} < \pi_j \), respectively. In this paper, we give an explicit formula for the generating function for the number of permutations of length \( n \) according to the number of upper, middle, lower rises, and upper, middle, lower descents. This allows us to recover several known results in the combinatorics of permutation patterns as well as many new results. For example, we give an explicit formula for the generating function for the number of permutations of length \( n \) having exactly \( m \) middle descents.
We prove that a sumset of a TE subset of N (these sets can be viewed as “aperiodic” sets) with a set of positive upper density intersects any polynomial sequence. For WM sets (subclass of TE sets) we prove that the intersection has lower Banach density one. In addition we obtain a generalization of the latter result to the case of several polynomials.
In this paper, we prove the Tiling implies Spectral part of Fuglede’s cojecture for the three interval case. Then we prove the converse Spectral implies Tiling in the case of three equal intervals and also in the case where the intervals have lengths 1/2, 1/4, 1/4. Next, we consider a set Ω ⊂ R, which is a union of n intervals. If Ω is a spectral set, we prove a structure theorem for the spectrum provided the spectrum is assumed to be contained in some lattice. The method of this proof has some implications on the Spectral implies Tiling part of Fuglede’s conjecture for three intervals. In the final step in the proof, we need a symbolic computation using Mathematica. Finally with one additional assumption we can conclude that the Spectral implies Tiling holds in this case.
We show that if \( A \) is a finite subset of an abelian group with additive energy at least \( c|A|^3 \), then there is a set \( \mathcal{L} \subset A \) with \( |\mathcal{L}| = O(c^{-1} \log |A|) \) such that \( |A \cap \mathrm{Span}(\mathcal{L})| = \Omega(c^{1/3} |A|) \).
We provide further explanation of the significance of an example in a recent paper of Wolf in the context of the problem of finding large subspaces in sumsets.
Lucy Slater used Bailey’s \( {}_6\psi_6 \) summation formula to derive the Bailey pairs she used to construct her famous list of 130 identities of the Rogers-Ramanujan type.
In the present paper, we apply the same techniques to Chu’s \( {}_{10}\psi_{10} \) generalization of Bailey’s formula to produce quite general Bailey pairs. Slater’s Bailey pairs are then recovered as special limiting cases of these more general pairs.
In re-examining Slater’s work, we find that her Bailey pairs are, for the most part, special cases of more general Bailey pairs containing one or more free parameters. Further, we also find new general Bailey pairs (containing one or more free parameters) which are also implied by the \( {}_6\psi_6 \) summation formula.
Slater used the Jacobi triple product identity (sometimes coupled with the quintuple product identity) to derive her infinite products. Here we also use other summation formulae (including special cases of the \( {}_6\psi_6 \) summation formula and Jackson’s \( {}_6\phi_5 \) summation formula) to derive some of our infinite products. We use the new Bailey pairs, and/or the summation methods mentioned above, to give new proofs of some general series-product identities due to Ramanujan, Andrews, and others. We also derive a new general series-product identity, one which may be regarded as a partner to one of the Ramanujan identities. We also find new transformation formulae between basic hypergeometric series, new identities of Rogers-Ramanujan type, and new false theta series identities. Some of these latter are a kind of “hybrid” in that one side of the identity consists of a basic hypergeometric series, while the other side is formed from a theta product multiplied by a false theta series. This type of identity appears to be new.
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 \( \langle \cdot, \cdot \rangle \) 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 \( \leq 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, \langle \cdot, \cdot \rangle) \), 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 = MM^* \), 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 \Lambda_1 + \cdots + \Lambda_k \), where \( \Lambda_i \) are dissociated sets. The exact upper bound for the number of solutions of the following equation:
\[
q_1 + \cdots + q_p = q_{p+1} + \cdots + q_{2p}, \quad q_i \in Q \tag{1}
\]
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 \geq 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 \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^\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^\infty \)-norms of the sums of such functions, where the sum is over rectangles of a fixed volume:
\[
n^{\eta(d)} \lesssim \Bigg\| \sum_{|R| = 2^{-n}} \alpha(R) h_R(x) \Bigg\|_{L^\infty([0,1]^d)}, \quad \text{for all } \eta(d) < \frac{d-1}{2} + \frac{1}{8d},
\]
where the implied constant is independent of \( n \geq 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) \).
We study the generating functions for pattern-restricted \(k\)-ary words of length \(n\) corresponding to the longest alternating subsequence statistic in which the pattern is any one of the six permutations of length three.
We extend an argument of Felix Behrend to show that fairly dense subsets of the integers exist which contain no solution to certain systems of linear equations.
Using combinatorial methods, we derive several formulas for the volume of convex bodies obtained by intersecting a unit hypercube with a halfspace, or with a hyperplane of codimension 1, or with a flat defined by two parallel hyperplanes. We also describe some of the history of these problems, dating to Polya’s Ph.D. thesis, and we discuss several applications of these formulas.
Let \( \mathbb{F}_2^n \) be the finite field of cardinality \( 2^n \). For all large \( n \), any subset \( A \subset \mathbb{F}_2^n \times \mathbb{F}_2^n \) of cardinality
\[
|A| \gtrsim \frac{4^n \log \log n}{\log n},
\]
must contain three points \( \{(x, y), (x + d, y), (x, y + d)\} \) for \( x, y, d \in \mathbb{F}_2^n \) and \( d \neq 0 \). Our argument is an elaboration of an argument of Shkredov [14], building upon the finite field analog of Ben Green [10]. The interest in our result is in the exponent on \( \log n \), which is larger than has been obtained previously.
In 1972, Bender and Knuth established a bijection between certain infinite matrices of non-negative integers and plane partitions and in [2] a bijection between Bender-Knuth matrices and n-color partitions was shown. Here we use this later bijection and translate the recently found n-color partition theoretic interpretations of four mock theta functions of S. Ramanujan in [1] to new combinatorial interpretations of the same mock theta functions involving Bender-Knuth matrices.
We present analytical properties of a sequence of integers related to the evaluation of a rational integral. We also discuss an algorithm for the evaluation of the 2-adic valuation of these integers that has a combinatorial interpretation.
It is proposed that finding the recursion relation and generating function for the (colored) Motzkin numbers of higher rank introduced recently is an interesting problem.
Let \( \mathbb{F}_2^n \) be the finite field of cardinality \( 2^n \). For all large \( n \), any subset \( A \subset \mathbb{F}_2^n \times \mathbb{F}_2^n \) of cardinality \[|A| \gtrsim \frac{4^n \log \log n}{\log n}, \] must contain three points \( \{(x, y), (x + d, y), (x, y + d)\} \) for \( x, y, d \in \mathbb{F}_2^n \) and \( d \neq 0 \). Our argument is an elaboration of an argument of Shkredov [14], building upon the finite field analog of Ben Green [10]. The interest in our result is in the exponent on \( \log n \), which is larger than has been obtained previously.
Let \( S \) be a finite set of positive integers with largest element \( m \). Let us randomly select a composition \( a \) of the integer \( n \) with parts in \( S \), and let \( m(a) \) be the multiplicity of \( m \) as a part of \( a \). Let \( 0 \leq r < q \) be integers, with \( q \geq 2 \), and let \( p_{n,r} \) be the probability that \( m(a) \) is congruent to \( r \mod q \). We show that if \( S \) satisfies a certain simple condition, then \( \lim_{n \to \infty} p_{n,r} = 1/q \). In fact, we show that an obvious necessary condition on \( S \) turns out to be sufficient.
This is an attempt of a comprehensive treatment of the results concerning estimates of the \( L^1 \)-norms of linear means of multiple Fourier series, the Lebesgue constants. Most of them are obtained by estimating the Fourier transform of a function generating such a method. Frequently the properties of the support of this function affect distinctive features in behavior of these norms. By this geometry enters and works hand-in-hand with analysis; moreover, the results are classified mostly in accordance with their geometrical nature. Not rarely Number Theory tools are brought in. We deal only with the trigonometric case – no generalizations for other orthogonal systems are discussed nor are applications to approximation. Several open problems are posed.
Let \( G \) be a finite abelian group and \( E \) a subset of it. Suppose that we know for all subsets \( T \) of \( G \) of size up to \( k \) for how many \( x \in G \) the translate \( x + T \) is contained in \( E \). This information is collectively called the \( k \)-deck of \( E \). One can naturally extend the domain of definition of the \( k \)-deck to include functions on \( G \). Given the group \( G \), when is the \( k \)-deck of a set in \( G \) sufficient to determine the set up to translation? The \( 2 \)-deck is not sufficient (even when we allow for reflection of the set, which does not change the \( 2 \)-deck) and the first interesting case is \( k = 3 \). We further restrict \( G \) to be cyclic and determine the values of \( n \) for which the \( 3 \)-deck of a subset of \( \mathbb{Z}_n \) is sufficient to determine the set up to translation. This completes the work begun by Grünbaum and Moore [GM] as far as the \( 3 \)-deck is concerned. We additionally estimate from above the probability that for a random subset of \( \mathbb{Z}_n \), there exists another subset, not a translate of the first, with the same \( 3 \)-deck. We give an exponentially small upper bound when the previously known one was \( O(1/\sqrt{n}) \).
Bourgain’s theorem says that under certain conditions a function \( f : \{0,1\}^n \to \{0,1\} \) can be approximated by a function \( g \) which depends only on a small number of variables. By following his proof we obtain a generalization for the case that there is a nonuniform product measure on the domain of \( f \).
Given integers \( s, t \), define a function \( \phi_{s,t} \) on the space of all formal series expansions by \(\phi_{s,t}\left(\sum a_n x^n\right) = \sum a_{sn+t} x^n.\) For each function \( \phi_{s,t} \), we determine the collection of all rational functions whose Taylor expansions at zero are fixed by \( \phi_{s,t} \). This collection can be described as a subspace of rational functions whose basis elements correspond to certain \( s \)-cyclotomic cosets associated with the pair \( (s, t) \).
In this note we use the theory of theta functions to discover formulas for the number of representations of N as a sum of three squares and for the number of representations of N as a sum of three triangular numbers. We discover various new relations between these functions and short, motivated proofs of well known formulas of related combinatorial and number-theoretic interest.
