Some properties and applications of non-trivial divisor functions

The jth divisor function \(d_j\), which counts the ordered factorisations of a positive integer into j positive integer factors, is a very well-known multiplicative arithmetic function. However, the non-multiplicative jth non-trivial divisor function\(c_j\), which counts the ordered factorisations of a positive integer into j factors each of which is greater than or equal to 2, is rather less well studied. Additionally, we consider the associated divisor function\(c_j^{(r)}\), for \(r\ge 0\), whose definition is motivated by the sum-over divisors recurrence for \(d_j\). We give an overview of properties of \(d_j\), \(c_j\) and \(c_j^{(r)}\), specifically regarding their Dirichlet series and generating functions as well as representations in terms of binomial coefficient sums and hypergeometric series. Noting general inequalities between the three types of divisor function, we then observe how their ratios can be expressed as binomial coefficient sums and hypergeometric series, and find explicit Dirichlet series and Euler products for some of these. As an illustrative application of the non-trivial and associated divisor functions, we show how they can be used to count principal reversible square matrices of the type considered by Ollerenshaw and Brée and so sum-and-distance systems of integers.

     

Symmetry and <Emphasis Type="Italic">p</Emphasis>-Stability

A symmetry of a game is a permutation of the player set and their strategy sets that leaves the payoff functions invariant. In this paper we introduce and discuss two relatively mild symmetry properties for set-valued solution concepts (that are equivalent when the solution concepts are single-valued) and show using examples that stable sets satisfy neither version. These examples also show that for every integer q, there exists a game with an equilibrium component of index q.Received February 2002/Revised November 2003Supported by an EPSRC doctoral grant.     

Sums of nilpotent matrices

We study matrices over general rings which are sums of nilpotent matrices. We show that over commutative rings all matrices with nilpotent trace are sums of three nilpotent matrices. We characterize 2-by-2 matrices with integer entries which are sums of two nilpotents via the solvability of a quadratic Diophantine equation. Some exemples in the case of matrices over noncommutative rings are given.     

Integer sets with distinct subset sums

We give a simple, elementary new proof of a generalization of the following conjecture of Paul Erdos: the sum of the elements of a finite integer set with distinct subset sums is less than 2.

     

一些同余问题的例外集合

利用特征和与指数和的估计,研究了一些同余问题的例外集合.具体来说,设p为充分大的素数,集合Y■Zp,正整数N相似文献   

An Enumerative Geometry for Magic and Magilatin Labellings

A magic labelling of a set system is a labelling of its points by distinct positive integers so that every set of the system has the same sum, the magic sum. Examples are magic squares (the sets are the rows, columns, and diagonals) and semimagic squares (the same, but without the diagonals). A magilatin labelling is like a magic labelling but the values need be distinct only within each set. We show that the number of n × n magic or magilatin labellings is a quasipolynomial function of the magic sum, and also of an upper bound on the entries in the square. Our results differ from previous ones because we require that the entries in the square all be different from each other, and because we derive our results not by ad hoc reasoning but from a general theory of counting lattice points in rational inside-out polytopes. We also generalize from set systems to rational linear forms. Dedicated to the memory of Claudia Zaslavsky, 1917–2006 Received August 10, 2005     

Conformal iterated function systems with applications to the geometry of continued fractions

In this paper we obtain some results about general conformal iterated function systems. We obtain a simple characterization of the packing dimension of the limit set of such systems and introduce some special systems which exhibit some interesting behavior. We then apply these results to the set of values of real continued fractions with restricted entries. We pay special attention to the Hausdorff and packing measures of these sets. We also give direct interpretations of these measure theoretic results in terms of the arithmetic density properties of the set of allowed entries.

     

The asymptotic number of labeled graphs with given degree sequences

Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: (i) each row sum is specified and bounded, (ii) the entries are bounded, and (iii) a specified “sparse” set of entries must be zero. The result can be interpreted in terms of incidence matrices for labeled graphs.     

算子稳定随机向量序列的一些极限结果

对于独立同分布的没有Gauss分量的指数为可逆线性算子A的算子稳定的R~d值随机向量序列,本文通过积分检验讨论了其部分和及加权和(包括一些经典的加权和,如Cesàro加权和,后置和方式,Euler可和方式,Borel可和方式,几何加权和等)的极限结果.由此得到了部分和及加权和在相对于A的谱分解下的Chover型重对数律,这是与A的特征值的实部有关的结果.     

On Integer Solutions to Linear Equations

A magic square is an n × n matrix with non-negative integer entries, such that the sum of the entries in each row and column is the same. We study the enumeration and P-recursivity of these in the case in which the sum along each row and column is fixed, with the size n of the matrix as the variable. A method is developed that nicely proves some known results about the case when the row and column sum is 2, and we prove new results for the case when the sum is 3. Received December 23, 2005     

Nash constructible functions

Nash constructible functions on a real algebraic set V are defined as linear combinations, with integer coefficients, of Euler characteristic of fibres of proper regular morphisms restricted to connected components of algebraic sets. We prove that if V is compact, these functions are sums of signs of semialgebraic arc-analytic functions (i.e. functions which become analytic when composed with any analytic arc). We also give a sharp upper bound to the number of semialgebraic arc-analytic functions which are necessary to define any given Nash constructible functions.     

On Sidon sets which are asymptotic bases

Let h ≧ 2 be an integer. We say that a set $ \mathcal{A} $ of positive integers is an asymptotic basis of order h if every large enough positive integer can be represented as the sum of h terms from $ \mathcal{A} $ . A set of positive integers $ \mathcal{A} $ is called a Sidon set if all the sums a + b with $ a \in \mathcal{A},b \in \mathcal{A},a \leqq b $ , are distinct. In this paper we prove the existence of Sidon sets which are asymptotic bases of order 5 by using probabilistic methods.     

Extended Bressoud-Wei and Koike skew Schur function identities

The Jacobi-Trudi identity expresses a skew Schur function as a determinant of complete symmetric functions. Bressoud and Wei extend this idea, introducing an integer parameter t?−1 and showing that signed sums of skew Schur functions of a certain shape are expressible once again as a determinant of complete symmetric functions. Koike provides a Jacobi-Trudi-style definition of universal rational characters of the general linear group and gives their expansion as a signed sum of products of Schur functions in two distinct sets of variables. Here we extend Bressoud and Wei's formula by including an additional parameter and extending the result to the case of all integer t. Then we introduce this parameter idea to the Koike formula, extending it in the same way. We prove our results algebraically using Laplace determinantal expansions.     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams

We consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). For general sets of entries, these numbers of matrices are not polynomials in q (Stembridge in Ann. Comb. 2(4):365, 1998); however, when the set of entries is a Young diagram, the numbers, up to a power of q?1, are polynomials with nonnegative coefficients (Haglund in Adv. Appl. Math. 20(4):450, 1998). In this paper, we give a number of conditions under which these numbers are polynomials in q, or even polynomials with nonnegative integer coefficients. We extend Haglund’s result to complements of skew Young diagrams, and we apply this result to the case where the set of entries is the Rothe diagram of a permutation. In particular, we give a necessary and sufficient condition on the permutation for its Rothe diagram to be the complement of a skew Young diagram up to rearrangement of rows and columns. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order.     

The asymptotic number of non-negative integer matrices with given row and column sums

Asymptotics are obtained for the number of m×n non-negative integer matrices subject to the following constraints: (i) each row and each column sum is specified and bounded, (ii) the entries are bounded, and (iii) a specified “sparse” set of entries must be zero. The result can be interpreted in terms of incidence matrices for labeled digraphs.     

$A$-序列倒数和的一个注记

An infinite integer sequence {1 ≤ a1 〈 a2 〈 ... } is called A-sequence, if no ai is sum of distinct members of the sequence other than ai. We give an example for the A-sequence, and the reciprocal sum of elements is∑1/ai〉 2.065436491, which improves slightly the related upper bounds for the reciprocal sums of sum-free sequences.     

VIP systems in partial semigroups

A VIP system is a polynomial-type generalization of the notion of an IP system, i.e., a set of finite sums. We extend the notion of VIP system to commutative partial semigroups and obtain an analogue of Furstenberg's central sets theorem for these systems which extends the polynomial Hales–Jewett Theorem of Bergelson and Leibman. Several Ramsey theoretic consequences, including the central sets theorem itself, are then derived from these results.     

Matrices with prescribed row and column sums

This is a survey of the recent progress and open questions on the structure of the sets of 0–1 and non-negative integer matrices with prescribed row and column sums. We discuss cardinality estimates, the structure of a random matrix from the set, discrete versions of the Brunn–Minkowski inequality and the statistical dependence between row and column sums.     

The Kernel of the Adjacency Matrix of a Rectangular Mesh

   Abstract. Given an m × n rectangular mesh, its adjacency matrix A , having only integer entries, may be interpreted as a map between vector spaces over an arbitrary field K . We describe the kernel of A : it is a direct sum of two natural subspaces whose dimensions are equal to