Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

On discount residue classes

It is shown that, whenever m₁, m₂,…, m_n are natural numbers such that the pairwise greatest common divisors, d_ij=(m_i, m_j), i≠j are distinct and different from 1, then there exist integers a₁, a₂,…,a_n such that the solution sets of the congruences x≡_i (modm_i), i= 1,2,…,n are disjoint.     

Symposium on combinatorial mathematics and optimal design

Let A₁,A₂,…,A_n be finite sets such that A_i?A_j for all i≠j. Let F be an intersecting family consisting of sets contained in some A_i, i=1,2,…,n. Chvátal conjectured that among the largest intersecting families, there is always a star. In this paper, we obtain another proof of a result of Schönheim: If A₁∩A₂∩?∩A_n≠?, then the conjecture is true. We also prove that if A_i∩A_jA_k = ? for all i≠j≠k≠i or if the independent system satisfies a hereditary tree structure, then the conjecture is also true.     

On ARX(∞) approximation

Given data, u_j,y_j,j=1,…,n, with u_j an input sequence to a system while output is y_j, an approximation to the structure of the system generating y_j is to be obtained by regressing y_j on u_j−i,y_j−ii=1,…,p_n, where p_n increases with n. In this paper the rate of convergence of the coefficient matrices to their asymptotic values is discussed. The context is kept general so that, in particular, u_j is allowed to depend on y_i, i≤j, and no assumption of stationarity for the y_j or u_j sequences is made.     

A conjecture of recski in combinatorial set theory

A p-cover of $\text{n = {1, 2,…,}\text{n}\text{}}$ is a family of subsets $\text{S}{}_{\mathrm{i}}\text{≠ ?}$ such that ∪ S_i = n and |S_i ∩ S_i| ? p for i ≠ j. We prove that for fixed p, the number of p-cover of n is O(n^p+1logn).     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

A stochastic permutation-flowshop scheduling problem minimizing in distribution the schedule length

Consider n jobs (J₁,J₂,…,J_n) and m machines (M₁,M₂…,M_m). Upon completion of processing of J_i, 1 ? i ? n, on M_j 1 ? j ? m ? 1, it departs with probability p_i or moves to M_j+1 with the complementary probability, 1?p_i. A job completing service on M_m departs. The processing time of j_i on M_j possesses a distribution function F_j. It is proved that sequencing the jobs in a nondecreasing order of p_i minimizes in distribution the schedule length.     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

Subsets of a finite set that intersect each other in at most one element

In this paper we study de Bruijn-Erdös type theorems that deal with the foundations of finite geometries. The following theorem is one of our main conclusions. Let S₁,…, S_n be n subsets of an n-set S. Suppose that |S_i| ? 3 (i = 1,…,n) and that |S_i ∩ S_j| ? 1 (i ≠ j;i,j = 1,…,n). Suppose further that each S_i has nonempty intersection with at least n ? 2 of the other subsets. Then the subsets S₁,…,S_n of S are one of the following configurations. (1) They are a finite projective plane. (2) They are a symmetric group divisible design and each subset has nonempty intersection with exactly n ? 2 of the other subsets. (3) We have n = 9 or n = 10 and in each case there exists a unique configuration that does not satisfy (1) or (2).     

Divisibility of determinants of power GCD matrices and power LCM matrices on finitely many quasi-coprime divisor chains

Let a, n ? 1 be integers and S = {x₁, … , x_n} be a set of n distinct positive integers. The matrix having the ath power (x_i, x_j)^a of the greatest common divisor of x_i and x_j as its i, j-entry is called ath power greatest common divisor (GCD) matrix defined on S, denoted by (S^a). Similarly we can define the ath power LCM matrix [S^a]. We say that the set S consists of finitely many quasi-coprime divisor chains if we can partition S as S = S₁ ∪ ? ∪ S_k, where k ? 1 is an integer and all S_i (1 ? i ? k) are divisor chains such that (max(S_i), max(S_j)) = gcd(S) for 1 ? i ≠ j ? k. In this paper, we first obtain formulae of determinants of power GCD matrices (S^a) and power LCM matrices [S^a] on the set S consisting of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. Using these results, we then show that det(S^a)∣det(S^b), det[S^a]∣det[S^b] and det(S^a)∣det[S^b] if a∣b and S consists of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. But such factorizations fail to be true if such divisor chains are not quasi-coprime.     

Fast canonization of circular strings

A circular string A = (a₁,…,a_n) is a string that has n equivalent linear representations A_i = a_i,…,a_n,a₁,…,a_i?1 for i = 1,…,n. The a_i's are assumed to be well ordered. We say that A_i < A_j if the word a_i…a_na₁…a_i?1 precedes the word a_j…a_na₁…a_j?1 in the lexicographic order, A_i ? A_j if either A_i < A_j or A_i = A_j. A_i0 is a minimal representation of A if A_i0 ? A_i for all 1 ≤ i ≤ n. The index i₀ is called a minimal starting point (m.s.p.). In this paper we discuss the problem of finding m.s.p. of a given circular string. Our algorithm finds, in fact, all the m.s.p.'s of a given circular string A of length n by using at most $\text{n + ?}\text{d}\text{2}\text{?}$ comparisons. The number d denotes the difference between two successive m.s.p.'s (see Lemma 1.1) and is equal to n if A has a unique m.s.p. Our algorithm improves the result of 3n comparisons given by K. S. Booth. Only constant auxiliary storage is used.     

An extremal problem for finite topologies and distributive lattices

Let (r₁, r₂, …) be a sequence of non-negative integers summing to n. We determine under what conditions there exists a finite distributive lattice L of rank n with r_i join-irreducibles of rank i, for all i = 1, 2, …. When L exists, we give explicit expressions for the greatest number of elements L can have of any given rank, and for the greatest total number of elements L can have. The problem is also formulated in terms of finite topological spaces.     

Prime links in some skew-polynomial and skew-laurent rings

Let R be a Noetherian commutative ring and a α₁,…,α_n commuting automorphisms of R. Define T = R[θ₁,…,θ_n;α₁,…,α_n] to be the skew-polynomial ring with θ_ir = α_i(r)θ_i and θ_iθ_j= θ_jθ_i, for all i,j ? (1,…,n) and r ? R, and let S = Rθ₁,θ₁:^-1,…,θ_n:,θ_n;^-1;α₁:,…,α_n] be the corresponding skew-Laurent ring. In this paper we show that S and T satisfy the strong second layer condition and characterize the links between prime ideals in these rings.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

Sperner systems consisting of pairs of complementary subsets

It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if $\text{A}$ = {;A₁,…, A_l}; consists of k-subsets of a set with n > 2k elements such that A_i ∩ A_j ≠ ? for all i, j then l ? (_k?1^n?1). Schönheim proved that if A₁, …, A_l are subsets of a set S with n elements such that A_i ? A_j, A_i ∩ A_j ≠ ø and A_i ∪ A_j ≠ S for all i ≠ j then $\text{l ? (}{}_{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]\; ?\; 1</mtext>}}{}^{\mathrm{n\; ?\; 1}}\text{)}$. In this note we prove a common strengthening of these results.     

On multi-coloured lines in a linear space

We prove that if X₁, X₂,…, X_k are pairwise disjoint sets of points in a linear space, each of cardinality n, whose union ∪_{j = 1}^kX_j, is not collinear, then there are at least (k ? 1) n lines in the space, which intersect at least two of th e X_j's. Equality occurs if and only if k = n + 1 and X₁,…, X_{n + 1} are obtained by taking n + 1 concurrent lines in a projective plane of order n, and omitting, from each of them, their common point. When n = 1, this reduces to a theorem of de Bruijn and Erdos (Indag. Math.10 (1984), 421–423).     

Bound on integrals: Elimination of the dual and reduction of the number of equality constraints

Let L_j (j = 1, …, n + 1) be real linear functions on the convex set $\text{F}$ of probability distributions. We consider the problem of maximization of L_n+1(F) under the constraint F ? $\text{F}$ and the equality constraints L₁(F) = z₁ (i = 1, …, n). Incorporating some of the equality constraints into the basic set $\text{F}$, the problem is equivalent to a problem with less equality constraints. We also show how the dual problems can be eliminated from the statement of the main theorems and we give a new illuminating proof of the existence of particular solutions.The linearity of the functions L_j(j = 1, …, n + 1) can be dropped in several results.     

Permanence and Positive Periodic Solutions for Kolmogorov Competing Species Systems

We prove the existence of periodic solutions in a compact attractor of (R⁺)ⁿ for the Kolmogorov system x′_i = x_if_i(t, x₁, …, x_n), i = l, …, n in the competitive case. Extension to differential delay equations are con- sidered too. Applications are given to Lotka-Volterra systems with periodic coefficients.     

Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

Number of Zeros of Diagonal Polynomials over Finite Fields

Let F be a finite field with q=pf elements, where p is a prime. Let N be the number of solutions (x1,…,xn) of the equation c1xd11+···+cnxdnn=c over the finite fields, where d1∣q−1, ciϵF*(i=1, 2,…,n), and cϵF. In this paper, we prove that if b1 is the least integer such that b1≥∑ni=1 (f/ri) (Di, p−1)/(p−1), then q[b1/f]−1∣N, where ri is the least integer such that di∣pri−1, Didi=pri−1, the (Di, p−1) denotes the greatest common divisor of Di and p−1, [b1/f] denotes the integer part of b1/f. If di=d, then this result is an improvement of the theorem that pb∣N, where b is an integer less than n/d, obtained by J. Ax (1969, Amer. J. Math.86, 255–261) and D. Wan (1988, Proc. AMS103, 1049–1052), under a certain natural restriction on d and n.