A study of the lex plus powers conjecture

An {a₁,…,a_n}-lex plus powers ideal is a monomial ideal in I⊂k[x₁,…,x_n] which minimally contains the regular sequence x₁^a₁,…,x_n^a_n and such that whenever m∈R_t is a minimal generator of I and m′∈R_t is greater than m in lex order, then m′∈I. Conjectures of Eisenbud et al. and Charalambous and Evans predict that after restricting to ideals containing a regular sequence in degrees {a₁,…,a_n}, then {a₁,…,a_n}-lex plus powers ideals have extremal properties similar to those of the lex ideal. That is, it is proposed that a lex plus powers ideal should give maximum possible Hilbert function growth (Eisenbud et al.), and, after fixing a Hilbert function, that the Betti numbers of a lex plus powers ideal should be uniquely largest (Charalambous, Evans). The first of these assertions would extend Macaulay's theorem on Hilbert function growth, while the second improves the Bigatti, Hulett, Pardue theorem that lex ideals have largest graded Betti numbers. In this paper we explore these two conjectures. First we give several equivalent forms of each statement. For example, we demonstrate that the conjecture for Hilbert functions is equivalent to the statement that for a given Hilbert function, lex plus powers ideals have the most minimal generators in each degree. We use this result to prove that it is enough to show that lex plus powers ideals have the most minimal generators in the highest possible degree. A similar result holds for the stronger conjecture. In this paper we also prove that if the weaker conjecture holds, then lex plus powers ideals are guaranteed to have largest socles. This suffices to show that the two conjectures are equivalent in dimension ?3, which proves the monomial case of the conjecture for Betti numbers in those degrees. In dimension 2, we prove both conjectures outright.     

The inversion formulae for automorphisms of polynomial algebras and rings of differential operators in prime characteristic

Let K be an arbitrary field of characteristic p>0. We find an explicit formula for the inverse of any algebra automorphism of any of the following algebras: the polynomial algebra P_n?K[x₁,…,x_n], the ring of differential operators D(P_n) on P_n, D(P_n)⊗P_m, the n’th Weyl algebra A_n or A_n⊗P_m, the power series algebra K[[x₁,…,x_n]], the subalgebra T_k1,…,kn of D(P_n) generated by P_n and the higher derivations , 0≤j<p^k_i, i=1,…,n (where k₁,…,k_n∈N), T_k1,…,kn⊗P_m or an arbitrary central simple (countably generated) algebra over an arbitrary field.     

Simultaneous solutions of Sylvester equations and idempotent matrices separating the joint spectrum

We investigate simultaneous solutions of the matrix Sylvester equations A_iX-XB_i=C_i,i=1,2,…,k, where {A₁,…,A_k} and {B₁,…,B_k} are k-tuples of commuting matrices of order m×m and p×p, respectively. We show that the matrix Sylvester equations have a unique solution X for every compatible k-tuple of m×p matrices {C₁,…,C_k} if and only if the joint spectra σ(A₁,…,A_k) and σ(B₁,…,B_k) are disjoint. We discuss the connection between the simultaneous solutions of Sylvester equations and related questions about idempotent matrices separating disjoint subsets of the joint spectrum, spectral mapping for the differences of commuting k-tuples, and a characterization of the joint spectrum via simultaneous solutions of systems of linear equations.     

S-Noetherian properties on amalgamated algebras along an ideal

Let A and B   be commutative rings with identity, f:A→B$f:A\to B$ a ring homomorphism and J an ideal of B  . Then the subring A?^fJ:={(a,f(a)+j)|a∈A and j∈J}$A{?}^{f}J:=\{(a,f(a)+j)|a\in A\text{and}j\in J\}$ of A×B$A\times B$ is called the amalgamation of A with B along with J with respect to f. In this paper, we investigate a general concept of the Noetherian property, called the S  -Noetherian property which was introduced by Anderson and Dumitrescu, on the ring A?^fJ$A{?}^{f}J$ for a multiplicative subset S   of A?^fJ$A{?}^{f}J$. As particular cases of the amalgamation, we also devote to study the transfers of the S  -Noetherian property to the constructions D+(_X1,…,_Xn)E[_X1,…,_Xn]$D+(X_1,\dots ,X_n)E[X_1,\dots ,X_n]$ and D+(_X1,…,_Xn)E?_X1,…,_Xn?$D+(X_1,\dots ,X_n)E?X_1,\dots ,X_n?$ and Nagata?s idealization.     

The minimum distance of sets of points and the minimum socle degree

Let K be a field of characteristic 0. Let be a reduced finite set of points, not all contained in a hyperplane. Let be the maximum number of points of Γ contained in any hyperplane, and let . If I⊂R=K[x₀,…,x_n] is the ideal of Γ, then in Tohaˇneanu (2009) [12] it is shown that for n=2,3, d(Γ) has a lower bound expressed in terms of some shift in the graded minimal free resolution of R/I. In these notes we show that this behavior holds true in general, for any n≥2: d(Γ)≥A_n, where A_n=min{a_i−n} and ⊕_iR(−a_i) is the last module in the graded minimal free resolution of R/I. In the end we also prove that this bound is sharp for a whole class of examples due to Juan Migliore (2010) [10].     

On questions related to saturated chains of primes in polynomial rings

We propose to give positive answers to the open questions: is R(X,Y) strong S when R(X) is strong S? is R stably strong S (resp., universally catenary) when R[X] is strong S (resp., catenary)? in case R is obtained by a (T,I,D) construction. The importance of these results is due to the fact that this type of ring is the principal source of counterexamples. Moreover, we give an answer to the open questions: is R〈X₁,…,X_n〉 residually Jaffard (resp., totally Jaffard) when R(X₁,…,X_n) is ? We construct a three-dimensional local ring R such that R(X₁,…,X_n) is totally Jaffard (and hence, residually Jaffard) whereas R〈X₁,…,X_n〉 is not residually Jaffard (and hence, not totally Jaffard).     

An algorithm for unimodular completion over Laurent polynomial rings

We present a new and simple algorithm for completion of unimodular vectors with entries in a multivariate Laurent polynomial ring over an infinite field K. More precisely, given n?3 and a unimodular vector V=^t(v₁,…,v_n)∈Rⁿ (that is, such that 〈v₁,…,v_n〉=R), the algorithm computes a matrix M in M_n(R) whose determinant is a monomial such that MV=^t(1,0,…,0), and thus M^-1 is a completion of V to an invertible matrix.     

Blocker sets, orthogonal arrays and their application to combination locks

Let A denote a set of order m and let X be a subset of A^k+1. Then X will be called a blocker (of A^k+1) if for any element say (a₁,a₂,…,a_k,a_k+1) of A^k+1, there is some element (x₁,x₂,…,x_k,x_k+1) of X such that x_i equals a_i for at least two i. The smallest size of a blocker set X will be denoted by α(m,k)and the corresponding blocker set will be called a minimal blocker. Honsberger (who credits Schellenberg for the result) essentially proved that α(2n,2) equals 2n² for all n. Using orthogonal arrays, we obtain precise numbers α(m,k) (and lower bounds in other cases) for a large number of values of both k and m. The case k=2 that is three coordinate places (and small m) corresponds to the usual combination lock. Supposing that we have a defective combination lock with k+1 coordinate places that would open if any two coordinates are correct, the numbers α(m,k) obtained here give the smallest number of attempts that will have to be made to ensure that the lock can be opened. It is quite obvious that a trivial upper bound for α(m,k) is m² since allowing the first two coordinates to take all the possible values in A will certainly obtain a blocker set. The results in this paper essentially prove that α(m,k) is no more than about m²/k in many cases and that the upper bound cannot be improved. The paper also obtains precise values of α(m,k) whenever suitable orthogonal arrays of strength two (that is, mutually orthogonal Latin squares) exist.     

Construction of nonnegative symmetric matrices with given spectrum

Let σ = (λ₁, … , λ_n) be the spectrum of a nonnegative symmetric matrix A with the Perron eigenvalue λ₁, a diagonal entry c and let τ = (μ₁, … , μ_m) be the spectrum of a nonnegative symmetric matrix B with the Perron eigenvalue μ₁. We show how to construct a nonnegative symmetric matrix C with the spectrum

(λ₁+max{0,μ₁-c},λ₂,…,λ_n,μ₂,…,μ_m).     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

On the span of Hadamard products of vectors

Let A₁, … , A_k be positive semidefinite matrices and B₁, … , B_k arbitrary complex matrices of order n. We show that

span{(A₁x)°(A₂x)°?°(A_kx)|x∈Cⁿ}=range(A₁°A₂°?°A_k)     

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.     

On the multiplicity and the Cohen-Macaulayness of fiber cones of graded algebras

Let A be a Noetherian local ring with the maximal ideal m and an m-primary ideal J. Let S=?_n≥0S_n be a finitely generated standard graded algebra over A. Set S⁺=?_n>0S_n. Denote by F_J(S)=?_n≥0→(S_n/JS_n) the fiber cone of S with respect to J. The paper characterizes the multiplicity and the Cohen-Macaulayness of F_J(S) in terms of minimal reductions of S⁺.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

On the Wronskian combinants of binary forms

Given a sequence A=(A₁,…,A_r) of binary d-ics, we construct a set of combinants C={C_q:0≤q≤r,q≠1}, to be called the Wronskian combinants of A. We show that the span of A can be recovered from C as the solution space of an SL(2)-invariant differential equation. The Wronskian combinants define a projective imbedding of the Grassmannian G(r,S_d), and, as a corollary, any other combinant of A is expressible as a compound transvectant in C.Our main result characterises those sequences of binary forms that can arise as Wronskian combinants; namely, they are the ones such that the associated differential equation has the maximal number of linearly independent polynomial solutions. Along the way we deduce some identities which relate Wronskians to transvectants. We also calculate compound transvectant formulae for C in the case r=3.     

Divisibility properties of power GCD matrices and power LCM matrices

Let a,b and n be positive integers and the set S={x₁,…,x_n} of n distinct positive integers be a divisor chain (i.e. there exists a permutation σ on {1,…,n} such that x_σ(1)|…|x_σ(n)). In this paper, we show that if a|b, then the ath power GCD matrix (S^a) 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 divides the bth power GCD matrix (S^b) in the ring M_n(Z) of n×n matrices over integers. We show also that if a?b and n?2, then the ath power GCD matrix (S^a) does not divide the bth power GCD matrix (S^b) in the ring M_n(Z). Similar results are also established for the power LCM matrices.     

On the monotonicity properties of additive representation functions, II

For a set A of positive integers and any positive integer n, let R₁(A,n), R₂(A,n) and R₃(A,n) denote the number of solutions of a+a^′=n with the additional restriction a,a^′∈A; a,a^′∈A,a<a^′ and a,a^′∈A,a≤a^′ respectively. In this paper, we specially focus on the monotonicity of R₃(A,n). Moreover, we show that there does not exist any set A⊂N such that R₂(A,n) or R₃(A,n) is eventually strictly increasing.     

Function algebras on which homomorphisms are point evaluations on sequences

In the study of the spectrum of a subalgebraA ofC(X), whereX is a completely regular Hausdorff space, a key question is, whether each homomorphism ?:A→R has the point evaluation property for sequences inA, that is whether, for each sequence (f _n ) inA, there exists a pointa inX such that ?(f _n )=f _n (a) for alln. In this paper it is proved that all algebras, which are closed under composition with functions inC ^∞ (R) and have a certain local property, have the point evaluation property for sequences. Such algebras are, for instance, the spaceC ^m (E) (m=0,1,...,∞) ofC ^m -functions on any real locally convex spaceE. This result yields in a trivial manner that each homomorphism ? onA is a point evaluation, ifX is Lindelöf or ifA contains a sequence which separates points inX. Further, also a well known result as well as some new ones are obtained as a consequence of the main theorem.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.