On a class of relatively prime sequences

For each natural number n, let a₀(n) = n, and if a₀(n),…,a_i(n) have already been defined, let a_i+1(n) > a_i(n) be minimal with (a_i+1(n), a₀(n) … a_i(n)) = 1. Let g(n) be the largest a_i(n) not a prime or the square of a prime. We show that g(n) ～ n and that $\text{g(n) > n + cn}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log}\text{(n)}$ for some c > 0. The true order of magnitude of g(n) ? n seems to be connected with the fine distribution of prime numbers. We also show that “most” a_i(n) that are not primes or squares of primes are products of two distinct primes. A result of independent interest comes of one of our proofs: For every sufficiently large n there is a prime $\text{p < n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ with [$\text{n}\text{p}$] composite.     

Quasi sure quadratic variation of local times of smooth semimartingales

In this paper, we prove that the process of the quadratic variation of local times of smooth semimartingales can be constructed as the quasi sure limit of the form ∑_Δn(L_t^a_i+1n−L_t^a_in)², where Δ_n=(a_iⁿ,a_i+1ⁿ) is a sequence of subdivisions of [a,b], a_iⁿ=i(b−a)/2ⁿ+a, i=0,1,…,2ⁿ.     

Least squares solutions to AX = B for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation

A matrix A∈R^n×n is called a bisymmetric matrix if its elements a_i,j satisfy the properties a_i,j=a_j,i and a_i,j=a_n-j+1,n-i+1 for 1?i,j?n. This paper considers least squares solutions to the matrix equation AX=B for A under a central principal submatrix constraint and the optimal approximation. A central principal submatrix is a submatrix obtained by deleting the same number of rows and columns in edges of a given matrix. We first discuss the specified structure of bisymmetric matrices and their central principal submatrices. Then we give some necessary and sufficient conditions for the solvability of the least squares problem, and derive the general representation of the solutions. Moreover, we also obtain the expression of the solution to the corresponding optimal approximation problem.     

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.     

On a partition problem of Frobenius

We consider the following problem, which was raised by Frobenius: Given n relatively prime positive integers, what is the largest integer M(a₁, a₂, …, a_n) omitted by the linear form Σ_i=1ⁿa_ix_i, where the x_i are variable nonnegative integers. We give the solution for certain special cases when n = 3.     

On the number of linear forms in logarithms

Let n be a positive integer. In this paper we estimate the size of the set of linear forms b₁loga₁+b₂loga₂+?+bnlogan, where |bi|?Bi and 1?ai?Ai are integers, as Ai,Bi→∞.     

Enumeration of sequences of given specification according to rises,falls and maxima

Letn = (a₁.a₂ … a_N) denote a sequence of integers a_i={1.2.…n}. A rise is a part a_i.a_i+1 with a_i <a_i+1: a fall is a pair with a_ia_i+1: a level is a pair with a_i = a_i+1. A maximum is a triple a_i-1.a_ia_i+1 with a_i-1?a_i.a_i?a_i+1. If e_i is the number of a_j?n witha_j = i, then [e₁…e_n] is called the specification of n. In addition, a conventional rise is counted to the left of a₁ and a conventional fall to the right of a_N: ifa₁?a₂, then a₁ is counted as a conventional maximum, similarly if a_N-1 ? a_N thena_N is a conventional maximum. Simon Newcomb's problem is to find the number of sequences n with given specification and r rises; the refined problem of determining the number of sequences of given specification with r rises and s falls has also been solved recently. The present paper is concerned with the problem of finding the number of sequences of given specification with r rises, s falls. λ levels and λ maxima. A generating function for this enumerant is obtained as the quotient of two continuants. In certain special cases this result simplifies considerably.     

Class G,and a unification problem

In 1958, Karl Goldberg proved the following: Theorem G. Suppose A=(a_ij) is an n×n matrix over the complex field, with the following properties: (1) a_ija_ji?0 for i,j=1,2,…,n, and (2) a_i1i2a_i2i3?a_isii=a_i2i1a_i3i2?a_i1is for all s=1,2,…,n and i_t=1,2,…,n. Then A has only real characteristic values. Definition. Let G_n denote the class of n×n matrices over $\text{C}$, the complex field, which satisfy the Goldberg conditions (1) and (2). We investigate some properties of class G related to the following topics: Schur complements, weak sign symmetry, and inequalities due to Oppenheim for positive definite matrices, and an analogue due to Markham for tridiagonal, oscillatory matrices.     

Nonhomogeneous spectra of numbers

A simple characterization is given of those sequences of integersM_n={a_i}ⁿ_i=1for which there exist real numbers αandβ such thata_i=?iα+β?(1?i?n). In addition, for givenM_n, an open intervalI_nis computed such that α?I_nif and only ifa_i=?iα+β?(1?i?n)for suitableβ=β(α).     

Some new results on the Littlewood-Offord problem

We consider the 2ⁿ sums of the form Σ?_ia_i with the a_i's vectors, | a_i | ? 1, and ?_i = 0, 1 for each i. We raise a number of questions about their distribution.We show that if the a_i lie in two dimensions, then at most $\text{n}\text{(}\text{n}\text{2}\text{)}$) sums can lie within a circle of diameter √3, and if n is even at most the sum of the three largest binomial coefficients can lie in a circle of diameter √5. These are best results under the indicated conditions.If two a's are more than 60° but less than 120° apart in direction, then the bound ($\text{n}\text{[}\text{n}\text{2}\text{]}$) on sums lying within a unit diameter sphere is improved to ($\text{n+1}\text{[}\text{n}\text{2}\text{]}\text{) ? 2(}\text{n?1}\text{[(n?}\text{1}\text{2}\text{)])}$.The method of Katona and Kleitman is shown to lead to a significant improvement on their two dimensional result.Finally, Lubell-type relations for sums lying in a unit diameter sphere are examined.     

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.     

On the number of complementary trees in a graph

Consider a graph with no loops or multiple arcs with n+1 nodes and 2n arcs labeled a_l,…,a_n,a′_l,…,a′_n, where n ≥ 5. A spanning tree of such a graph is called complementary if it contains exactly one arc of each pair {a_i,a′_i}. The purpose of this paper is to develop a procedure for finding complementary trees in a graph, given one such tree. Using the procedure repeatedly we give a constructive proof that every graph of the above form which has one complementary tree has at least six such trees.     

On additive representation function of general sequences

Let 0 ≦ a ₁ < a ₂ < ? be an infinite sequence of integers and let r ₁(A, n) = |(i;j): a _i + a _j = n, i ≦ j|. We show that if d > 0 is an integer, then there does not exist n ₀ such that d ≦ r ₁ (A, n) ≦ d + [√2d + ½] for n > n ₀.     

A linear algorithm for nonhomogeneous spectra of numbers

Given a sequence of integers [a_i]_i=1ⁿ, an O(n) iterative algorithm is presented which decides whether there exist real numbers α and β such that a_i = [iα + β] (1 ? i ? n). In fact, the linear algorithm computes the partial quotients of the continued fraction expansions of $\text{d}$ and $\text{d}$ such that $\text{d < α <}\text{d}$ if and only if a_i = [iα + β] (1 ? i ? n) for suitable β = β(α).     

Construction of a Jacobi matrix from spectral data

A proof is given for the existence and uniqueness of a correspondence between two pairs of sequences {a},{b} and {ω},{μ}, satisfying b_i>0 for i=1,…,n?1 and ω₁<μ₁<?<μ_n?1<ω_n, under which the symmetric Jacobi matrices J(n,a,b) and J(n?1,a,b) have eigenvalues {ω} and {μ} respectively. Here J(m,a,b) is symmetric and tridiagonal with diagonal elements a_i (i=1,…,m) and off diagonal elements b_i (i=1,…,m?1). A new concise proof is given for the known uniqueness result. The existence result is new.     

Pelikán's conjecture and cyclotomic cosets

The following conjecture was recently made by J. Pelikán. Let a₀ ,…, a_n be an (n + 1)-tuple of 0's and 1's; let A_k = ?_i=0^n?ka_ia_i+k for k = 0,…, n. Then if n ? 4 some A_k is even.This paper shows that Pelikán's conjecture is false for infinitely many values of n. On the other hand it is also shown that the conjecture is true for most values of n, and a characterization is given of those values of n for which it fails.     

Behrend's theorem for sequences containing no k-element arithmetic progression of a certain type

Let k and n be positive integers, and let d(n, k) be the maximum density in {0, 1, 2,…, kⁿ ? 1} of a set containing no arithmetic progression of k terms with first term a = Σa_ikⁱ and common difference d = Σ?_ikⁱ, where 0 ? a_i ? k ? 1, ?_i = 0 or 1, and ?_i = 1 ? a_i = 0. Setting β_k = lim_n→∞d(n, k), we show that lim_k→∞β_k is either 0 or 1.     

On diagonal products of doubly stochastic matrices

The following result is proved: If A and B are distinct n × n doubly stochastic matrices, then there exists a permutation σ of {1, 2,…, n} such that ∏_ia_iσ(i) > ∏_ib_iσ(i).     

Representations of lattices via neutral elements

For any neutral element a in a bounded latticeL, the mapping x→(x∧,x∨a) representsL as a subdirect product of [0, a]×[a, 1]. It is first shown that for certain neutral elements, the image ofL under this mapping is completely determined by a homomorphism of [0, a] into [a, 1]. Iterating this process, a representation ofL can be obtained as a subdirect product of the intervals [a_i, a_i+1] for any chain 0=a₀1... nn+1=1 where each a_i is such a neutral element relative to [0, a_i+1]. The image in this case is completely determined by a family of homomorphisms π_i,j:A_i →A_j(ii=[a_i, a_i+1].     

A note on scheduling identical coupled tasks in logarithmic time

The coupled tasks problem consists in scheduling n jobs on a single machine. Each job i is made of two operations with processing times a_i and b_i and a fixed required delay L_i between them. Operations cannot overlap in time but operations of different jobs can be interleaved. The objective is to minimize the makespan of the schedule. In this note we show that the problem with identical jobs (∀i,a_i=a,b_i=b,L_i=L) can be solved in O(logn) time when a,b,L are fixed. This problem is motivated by radar scheduling applications where tasks corresponding to transmitting radiowaves and listening to potential echoes are coupled.