Overdetermined linear systems satisfying nonnegativity constraints

Let A be a nonnegative m × n matrix, and let b be a nonnegative vector of dimension m. Also, let S be a subspace of $\text{R}$ⁿ such that if P_S is the orthogonal projector onto S, then P_S ? 0. A necessary condition is given for the matrix A to satisfy the following property: For all b ? 0, if min[boxV]b ? Ax[boxV] is attained at x = x₀, then x₀ ? 0 and x₀ ? S. It is also shown that if a nonnegative matrix A has a nonnegative generalized inverse, then any submatrix of A also possesses a nonnegative generalized inverse.     

Small solutions of linear Diophantine equations

Let Ax = B be a system of m × n linear equations with integer coefficients. Assume the rows of A are linearly independent and denote by X (respectively Y) the maximum of the absolute values of the m × m minors of the matrix A (the augmented matrix (A, B)). If the system has a solution in nonnegative integers, it is proved that the system has a solution X = (x_i) in nonnegative integers wity x_i ⩽ X for n - m variables and x_i ⩽ (m - m + 1)Y for m variables. This improves previous results of the authors and others.     

Bases and nonbases of square-free integers

A basis is a set A of nonnegative integers such that every sufficiently large integer n can be represented in the form n = a_i + a_j with a_i, a_i ∈ A. If A is a basis, but no proper subset of A is a basis, then A is a minimal basis. A nonbasis is a set of nonnegative integers that is not a basis, and a nonbasis A is maximal if every proper superset of A is a basis. In this paper, minimal bases consisting of square-free numbers are constructed, and also bases of square-free numbers no subset of which is minimal. Maximal nonbases of square-free numbers do not exist. However, nonbases of square-free numbers that are maximal with respect to the set of square-free numbers are constructed, and also nonbases of square-free numbers that are not contained in any nonbasis of square-free numbers maximal with respect to the square-free numbers.     

A subgroup involvement of the Fibonacci length

For a non-Abelian 2-generated finite group G=〈a,b〉, the Fibonacci length of G with respect to A={a,b}, denoted by LEN _A (G), is defined to be the period of the sequence x ₁=a,x ₂=b,x ₃=x ₁ x ₂,…,x _n+1=x _n?1 x _n ,… of the elements of G. For a finite cyclic group C _n =〈a〉, LEN _A (C _n ) is defined in a similar way where A={1,a} and it is known that LEN _A (C _n )=k(n), the well-known Wall number of n. Over all of the interesting numerical results on the Fibonacci length of finite groups which have been obtained by many authors since 1990, an intrinsic property has been studied in this paper. Indeed, by studying the family of minimal non-Abelian p-groups it will be shown that for every group G of this family, there exists a suitable generating set A′ for the derived subgroup G′ such that LEN _A′(G′)|LEN _A (G) where, A is the original generating set of G.     

A test for conjugacy of partitions of finite sets

In this note we present a simple test, involving a sequence of integers, which assures the conjugacy of a given partition P of a finite set S when our operations lead only to nonnegative integers. If negative integers appear in our operations, our test is inconclusive. The test, when conclusive, and an elementary property of permutations determine a conjugate for P.     

Divisibility properties of power LCM matrices by power GCD matrices on gcd-closed sets

Let e and n be positive integers and S={x₁,…,x_n} a set of n distinct positive integers. For x∈S, define . The n×n matrix whose (i,j)-entry is the eth power (x_i,x_j)^e of the greatest common divisor of x_i and x_j is called the eth power GCD matrix on S, denoted by (S^e). Similarly we can define the eth power LCM matrix [S^e]. Bourque and Ligh showed that (S)∣[S] holds in the ring of n×n matrices over the integers if S is factor closed. Hong showed that for any gcd-closed set S with |S|≤3, (S)∣[S]. Meanwhile Hong proved that there is a gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S)?[S]. In this paper, we introduce a new method to study systematically the divisibility for the case max_x∈S{|G_S(x)|}≤2. We give a new proof of Hong’s conjecture and obtain necessary and sufficient conditions on the gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S^e)|[S^e]. This partially solves an open question raised by Hong. Furthermore, we show that such factorization holds if S is a gcd-closed set such that each element is a prime power or the product of two distinct primes, and in particular if S is a gcd-closed set with every element less than 12.     

On the growth of the counting function of Stanley sequences

Given a finite set of nonnegative integers A with no three-term arithmetic progressions, the Stanley sequence generated by A, denoted as S(A), is the infinite set created by beginning with A and then greedily including strictly larger integers which do not introduce a three-term arithmetic progression in S(A). Erd?s et al. asked whether the counting function, S(A,x), of a Stanley sequence S(A) satisfies for every ?>0 and x>x₀(?,A). In this paper we answer this question in the affirmative; in fact, we prove the slightly stronger result that for x≥x₀(?,A).     

Sets whose sumset avoids a thin sequence

Let {a₁,a₂,a₃,…} be an unbounded sequence of positive integers with an+1/an approaching α as n→∞, and let β>max(α,2). We show that for all sufficiently large x?0, if A⊂[0,x] is a set of nonnegative integers containing 0 and satisfying

     

Sets of periods for automorphisms of compact Riemann surfaces

Let G=〈f〉 be a finite cyclic group of order N that acts by conformal automorphisms on a compact Riemann surface S of genus g≥2. Associated to this is a set A of periods defined to be the subset of proper divisors d of N such that, for some x∈S, x is fixed by f^d but not by any smaller power of f. For an arbitrary subset A of proper divisors of N, there is always an associated action and, if g_A denotes the minimal genus for such an action, an algorithm is obtained here to determine g_A. Furthermore, a set A_max is determined for which g_A is maximal.     

The endomorphism spectrum of a monounary algebra

The endomorphism spectrum specA of an algebra A is defined as the set of all positive integers, which are equal to the number of elements in an endomorphic image of A, for all endomorphisms of A. In this paper we study finite monounary algebras and their endomorphism spectrum. If a finite set S of positive integers is given, one can look for a monounary algebra A with S = specA. We show that for countably many finite sets S, no such A exists. For some sets S, an appropriate A with spec A = S are described. For n ∈ ? it is easy to find a monounary algebra A with {1, 2, ..., n} = specA. It will be proved that if i ∈ ?, then there exists a monounary algebra A such that specA skips i consecutive (consecutive eleven, consecutive odd, respectively) numbers. Finally, for some types of finite monounary algebras (binary and at least binary trees) A, their spectrum is shown to be complete.     

A theorem of the transversal theory for matroids of finite character

Let M = (S, I) be a matroid of finite character on the infinite set S. Let $\text{A}\text{= 〈A}{}_1\text{:i ∈ I〉}$ be any system of subsets of S each having finite rank and let $\text{B}\text{= 〈B}{}_1\text{: j ∈ J〉}$ be a finite system of sets of arbitrary rank. Necessary and sufficient conditions are given for the system $\text{A}$ ? $\text{B}$ to have an independent system of distinct representatives.     

Modular retractions of numerical semigroups

Let S be a numerical semigroup, let m be a nonzero element of S, and let a be a nonnegative integer. We denote ${\rm R}(S,a,m) = \{ s-as \bmod m \mid s \in S \}$ (where asmodm is the remainder of the division of as by m). In this paper we characterize the pairs (a,m) such that ${\rm R}(S,a,m)$ is a numerical semigroup. In this way, if we have a pair (a,m) with such characteristics, then we can reduce the problem of computing the genus of S=〈n ₁,…,n _p 〉 to computing the genus of a “smaller” numerical semigroup 〈n ₁?an ₁modm,…,n _p ?an _p modm〉. This reduction is also useful for estimating other important invariants of S such as the Frobenius number and the type.     

Nonnegative rank-preserving operators

Analogues of characterizations of rank-preserving operators on field-valued matrices are determined for matrices witheentries in certain structures $\text{S}$ contained in the nonnegative reals. For example, if $\text{S}$ is the set of nonnegative members of a real unique factorization domain (e.g. the nonnegative reals or the nonnegative integers), M is the set of m×n matrices with entries in $\text{S}$, and min(m,n)?4, then a “linear” operator on M preserves the “rank” of each matrix in M if and only if it preserves the ranks of those matrices in M of ranks 1, 2, and 4. Notions of rank and linearity are defined analogously to the field-valued concepts. Other characterizations of rank-preserving operators for matrices over these and other structures $\text{S}$ are also given.     

Sums and products with smooth numbers

We estimate the sizes of the sumset A+A and the productset A⋅A in the special case that A=S(x,y), the set of positive integers n?x free of prime factors exceeding y.     

Testing integer knapsacks for feasibility

We present a new approach for determining whether there exist nonnegative integers x₁, x₂, …, x_n satisfying a₁x₁ + a₂x₂ + ? + a_nx_n = b, where a₁ < a₂ < ? < a_n and b are nonnegative integers. case time complexity is analyzed and compared with dynamic programming techniques. Computational results are given.     

On the Möbius function of the locally finite poset associated with a numerical semigroup

Let S be a numerical semigroup and let (?,≤ _S ) be the (locally finite) poset induced by S on the set of integers ? defined by x≤ _S y if and only if y?x∈S for all integers x and y. In this paper, we investigate the Möbius function associated to (?,≤ _S ) when S is an arithmetic semigroup.     

On integers which are the sum of a power of 2 and a polynomial value

Here, we show that if f (x) ∈ ?[x] has degree at least 2 then the set of integers which are of the form 2 ^k + f (m) for some integers k ≥ 0 and m is of asymptotic density 0. We also make some conjectures and prove some results about integers not of the form |2 ^k ± m ^a (m ? 1)|.     

A note on a special case of the Frobenius problem

For a set of positive and relative prime integers A = {a ₁…,a _k }, let Γ(A) denote the set of integers of the form a ₁ x ₁+…+a _k x _k with each x _j ≥ 0. Let g(A) (respectively, n(A) and s(A)) denote the largest integer (respectively, the number of integers and sum of integers) not in Γ(A). Let S*(A) denote the set of all positive integers n not in Γ(A) such that n + Γ(A) \ {0} ? Γ((A)\{0}. We determine g(A), n(A), s(A), and S*(A) when A = {a, b, c} with a | (b + c).     

The Frobenius problem, sums of powers of integers, and recurrences for the Bernoulli numbers

In the Frobenius problem with two variables, one is given two positive integers a and b that are relative prime, and is concerned with the set of positive numbers NR that have no representation by the linear form ax+by in nonnegative integers x and y. We give a complete characterization of the set NR, and use it to establish a relation between the power sums over its elements and the power sums over the natural numbers. This relation is used to derive new recurrences for the Bernoulli numbers.     

Equidistribution of numerical semigroup gaps modulo m

For a positive integer m, a finite set of integers is said to be equidistributed modulo m if the set contains an equal number of elements in each congruence class modulo m. In this paper, we consider the problem of determining when the set of gaps of a numerical semigroup S is equidistributed modulo m. Of particular interest is the case when the nonzero elements of an Apéry set of S form an arithmetic sequence. We explicitly describe such numerical semigroups S and determine conditions for which the sets of gaps of these numerical semigroups are equidistributed modulo m.