More on planar point subsets with a specified number of interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let g(k) be the smallest integer such that every set P of points in the plane with no three collinear points and with at least g(k) interior points has a subset containing precisely k interior point of P. We prove that g(k) ≥ 3k for k ≥ 3, which improves the known result that g(k) ≥ 3k ? 1 for k ≥ 3.     

On q-multiplicative functions taking a fixed value on set of primes

The following assertion is proved. Let gbe a q-multiplicative function for which |g(n)| = 1 for every integer, and g(p) = constantfor every large prime p. Then there is some integer kin [1; c] such that g ^k(nq) = 1 for every n∈ N. Here cis a suitable absolute constant.     

Polynomials and primitive roots in finite fields

The primitive elements of a finite field are those elements of the field that generate the multiplicative group of k. If f(x) is a polynomial over k of small degree compared to the size of k, then f(x) represents at least one primitive element of k. Also f(x) represents an lth power at a primitive element of k, if l is also small. As a consequence of this, the following results holds.Theorem. Let g(x) be a square-free polynomial with integer coefficients. For all but finitely many prime numbers p, there is an integer a such that g(a) is equivalent to a primitive element modulo p.Theorem. Let l be a fixed prime number and f(x) be a square-free polynomial with integer coefficients with a non-zero constant term. For all but finitely many primes p, there exist integers a and b such that a is a primitive element and f(a) ≡ b¹ modulo p.     

Almost Primitive Elements of Free lie Algebras of Small Ranks

Let K be a field, X = {x1, . . . , xn}, and let L(X) be the free Lie algebra over K with the set X of free generators. A. G. Kurosh proved that subalgebras of free nonassociative algebras are free, A. I. Shirshov proved that subalgebras of free Lie algebras are free. A subset M of nonzero elements of the free Lie algebra L(X) is said to be primitive if there is a set Y of free generators of L(X), L(X) = L(Y ), such that M ? Y (in this case we have |Y | = |X| = n). Matrix criteria for a subset of elements of free Lie algebras to be primitive and algorithms to construct complements of primitive subsets of elements with respect to sets of free generators have been constructed. A nonzero element u of the free Lie algebra L(X) is said to be almost primitive if u is not a primitive element of the algebra L(X), but u is a primitive element of any proper subalgebra of L(X) that contains it. A series of almost primitive elements of free Lie algebras has been constructed. In this paper, for free Lie algebras of rank 2 criteria for homogeneous elements to be almost primitive are obtained and algorithms to recognize homogeneous almost primitive elements are constructed.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

Birational composition of quadratic forms over a local field

Let f(X) and g(Y) be nondegenerate quadratic forms of dimensions m and n, respectively, over K, char K ≠ 2. The problem of birational composition of f(X) and g(Y) is considered: When is the product f(X) · g(Y) birationally equivalent over K to a quadratic form h(Z) over K of dimension m + n? The solution of the birational composition problem for anisotropic quadratic forms over K in the case of m = n = 2 is given. The main result of the paper is the complete solution of the birational composition problem for forms f(X) and g(Y) over a local field P, char P ≠ 2.     

On digit sums of multiples of an integer

Let g>1 be an integer and sg(m) be the sum of digits in base g of the positive integer m. In this paper, we study the positive integers n such that sg(n) and sg(kn) satisfy certain relations for a fixed, or arbitrary positive integer k. In the first part of the paper, we prove that if n is not a power of g, then there exists a nontrivial multiple of n say kn such that sg(n)=sg(kn). In the second part of the paper, we show that for any K>0 the set of the integers n satisfying sg(n)?Ksg(kn) for all k∈N is of asymptotic density 0. This gives an affirmative answer to a question of W.M. Schmidt.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

On the fluctuations of independent copies of moving maxima

Let {X_n, n1} be a sequence of independent random variables (r.v.'s) with a common distribution function (d.f.) F. Define the moving maxima Y_k(n)=max(X_n−k(n)+1,X_n−k(n)+2,…,X_n), where {k(n), n1} is a sequence of positive integers. Let Y_k(n)¹ and Y_k(n)² be two independent copies of Y_k(n). Under certain conditions on F and k(n), the set of almost sure limit points of the vector consisting of properly normalised Y_k(n)¹ and Y_k(n)² is obtained.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

A Drazin inverse for rectangular matrices

The definition of the Drazin inverse of a square matrix with complex elements is extended to rectangular matrices by showing that for any B and W,m by n and n by m, respectively, there exists a unique matrix, X, such that (BW)^k=(BW)^k+1XW for some positive integer k, XWBWX = X, and BWX = XWB. Various expressions satisfied by B, W,X and related matrices are developed.     

Disjoint factors of diameter two in complete graphs

Let f(k) be the least positive integer n such that the complete graph with n vertices has a decomposition into k factors of diameter two. It is well known that f(2) = 5, f(3) = 12 or 13, and 4k ?1 ? f(k) ? 7k for every integer k ? 4. In the present paper it is proved that 6k ? 52 ? f(k) ? 6k for every integer k ? 2. (For k ? 370 also a better lower estimate of f(k) is given.)     

More on an Erdős–Szekeres-Type Problem for Interior Points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k≥1, let g(k) be the smallest integer such that every planar point set in general position with at least g(k) interior points has a convex subset of points with exactly k interior points of P. In this article, we prove that g(3)=9.     

Arrangements of n Points whose Incident-Line-Numbers are at most n/2

We consider a set X of n noncollinear points in the Euclidean plane, and the set of lines spanned by X, where n is an integer with n ≥ 3. Let t(X) be the maximum number of lines incident with a point of X. We consider the problem of finding a set X of n noncollinear points in the Euclidean plane with t(X) ￡ ?n/2 ?{t(X) \le \lfloor n/2 \rfloor}, for every integer n ≥ 8. In this paper, we settle the problem for every integer n except n = 12k + 11 (k ≥ 4). The latter case remains open.     

On the root closedness of continuous function algebras

For a compact Hausdorff space X, C(X) denotes the algebra of all complex-valued continuous functions on X. For a positive integer n, we say that C(X) is n-th root closed if, for each f∈C(X), there exists g∈C(X) such that f=gn. It is shown that, for each integer m?2, there exists a compact Hausdorff space Xm such that C(Xm) is m-th root closed, but not n-th root closed for each integer n relatively prime to m. This answers a question posed by Countryman Jr. [R.S. Countryman Jr., On the characterization of compact Hausdorff X for which C(X) is algebraically closed, Pacific J. Math. 20 (1967) 433-438] et al.     

Limiting distributions of functionals of Markov chains

Let \s{X_n, n ? 0\s} and \s{Y_n, n ? 0\s} be two stochastic processes such that Y_n depends on X_n in a stationary manner, i.e. P(Y_n ? A\vbX_n) does not depend on n. Sufficient conditions are derived for Y_n to have a limiting distribution. If X_n is a Markov chain with stationary transition probabilities and Y_n = f(X_n,..., X_n+k) then Y_n depends on X_n is a stationary way. Two situations are considered: (i) \s{X_n, n ? 0\s} has a limiting distribution (ii) \s{X_n, n ? 0\s} does not have a limiting distribution and exits every finite set with probability 1. Several examples are considered including that of a non-homogeneous Poisson process with periodic rate function where we obtain the limiting distribution of the interevent times.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

Sperner families over a subset

Let |X| = n > 0, |Y| = k > 0, and Y ? X. A family A of subsets of X is a Sperner family of X over Y if A₁A₂ for every pair of distinct members of A and every member of A has a nonempty intersection with Y. The maximum cardinality f(n, k) of such a family is determined in this paper. $\text{f(n,k)=(}\text{n}\text{[n}\text{2]}\text{)?(}\text{?k}\text{[n}\text{2]}\text{)}$.     

Some applications of Montgomery's sieve

Artin has conjectured that every positive integer not a perfect square is a primitive root for some odd prime. A new estimate is obtained for the number of integers in the interval [M + 1, M + N] which are not primitive roots for any odd prime, improving on a theorem of Gallagher.Erd?s has conjectured that 7, 15, 21, 45, 75, and 105 are the only values of the positive integer n for which n ? 2^k is prime for every k with 1 ≤ k ≤ log₂n. An estimate is proved for the number of such n ≤ N.     

On the existence of a point subset with three or five interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let h(k) be the smallest integer such that every point set in the plane, no three collinear, with at least h(k) interior points, has a subset with k or k + 2 interior points of P. We prove that h(3) = 8.