Analytic representations in the three-dimensional Frobenius problem

We consider the Diophantine problem of Frobenius for the semigroup , where d ³ denotes the triple (d ₁,d ₂,d ₃), gcd (d ₁,d ₂,d ₃)=1. Based on the Hadamard product of analytic functions, we find the analytic representation of the diagonal elements a _kk (d ³) of Johnson’s matrix of minimal relations in terms of d ₁, d ₂, and d ₃. With our recent results, this gives the analytic representation of the Frobenius number F(d ³), genus G(d ³), and Hilbert series H(d ³;z) for the semigroups . This representation complements Curtis’s theorem on the nonalgebraic representation of the Frobenius number F(d ³). We also give a procedure for calculating the diagonal and off-diagonal elements of Johnson’s matrix.      

A Note on Graph Pebbling

 We say that a graph G is Class 0 if its pebbling number is exactly equal to its number of vertices. For a positive integer d, let k(d) denote the least positive integer so that every graph G with diameter at most d and connectivity at least k(d) is Class 0. The existence of the function k was conjectured by Clarke, Hochberg and Hurlbert, who showed that if the function k exists, then it must satisfy k(d)=Ω(2 ^d /d). In this note, we show that k exists and satisfies k(d)=O(2 ^2d ). We also apply this result to improve the upper bound on the random graph threshold of the Class 0 property. Received: April 19, 1999 Final version received: February 15, 2000     

On Sequential Fixed-Size Confidence Regions for the Mean Vector

In order to construct a fixed-size confidence region for the mean vector of an unknown distribution functionF, a new purely sequential sampling strategy is proposed first. For this new procedure, under some regularity conditions onF, the coverage probability is shown (Theorem 2.1) to be at least (1−α)−Bα²d²+o(d²) asd→0, where (1−α) is the preassigned level of confidence,Bis an appropriate functional ofF, and 2dis the preassigned diameter of the proposed spherical confidence region for the mean vector ofF. An accelerated version of the stopping rule is also provided with the analogous second-order characteristics (Theorem 3.1). In the special case of ap-dimensional normal random variable, analogous purely sequential and accelerated sequential procedures as well as a three-stage procedure are briefly introduced together with their asymptotic second-order characteristics.     

Atoms of the set of numerical semigroups with fixed Frobenius number

Given a positive integer g, we denote by F(g) the set of all numerical semigroups with Frobenius number g. The set (F(g),∩) is a semigroup. In this paper we study the generators of this semigroup.     

Quadratic forms which have only large zeros

We give lower bounds for zeros of quadratic forms. For example, givenn2d>0 there are infinitely many nonsingular quadratic formsF with integral coefficients inn variables which vanish on ad-dimensional rational subspace such that anyn linearly independent integral zerosx ₁,...,x _n satisfy |x ₁|...|x _n |F(ⁿ²/^2d)–d, whereF is the maximum modulus of the coefficients ofF. This complements a recent result of the authors in the opposite direction and shows that it is best possible.Written whileSchmidt had a Senior Scientist Award from the Alexander von Humboldt-Stiftung in the Federal Republic of Germany.     

Consistency on cubic lattices for determinants of arbitrary orders

We introduce a class of k-potential submanifolds in pseudo-Euclidean spaces and prove that for an arbitrary positive integer k and an arbitrary nonnegative integer p, each N-dimensional Frobenius manifold can always be locally realized as an N-dimensional k-potential submanifold in ((k + 1)N + p)-dimensional pseudo-Euclidean spaces of certain signatures. For k = 1 this construction was proposed by the present author in a previous paper (2006). The realization of concrete Frobenius manifolds is reduced to solving a consistent linear system of second-order partial differential equations.     

Expected Frobenius numbers

Given a primitive positive integer vector a, the Frobenius number F(a) is the largest integer that cannot be represented as a non-negative integral combination of the coordinates of a. We show that for large instances the order of magnitude of the expected Frobenius number is (up to a constant depending only on the dimension) given by its lower bound.     

Frobenius problem for semigroups \mathsf{S}(d_{1},d_{2},d_{3})

We find the matrix representation of the set Δ(d ³), where d ³=(d ₁,d ₂,d ₃), of integers that are unrepresentable by d ₁,d ₂,d ₃ and develop a diagrammatic procedure for calculating the generating function Φ(d ³;z) for the set Δ(d ³). We find the Frobenius number F(d ³), the genus G(d ³), and the Hilbert series H(d ³;z) of a graded subring for nonsymmetric and symmetric semigroups and enhance the lower bounds of F(d ³) for symmetric and nonsymmetric semigroups.      

On the torsion in K_2 of a field

For a field F,let Gn(F) = {{a,Φn(a)} ∈ K2(F) | a,Φn(a) ∈ F*},where Φn(x) is the n-th cyclotomic polynomial.At first,by using Faltings' theorem on Mordell conjecture it is proved that if F is a number field and if n = 4,8,12 is a positive integer having a square factor then Gn(F) is not a subgroup of K2(F),and then by using the results of Manin,Grauert,Samuel and Li on Mordell conjecture theorem for function fields,a similar result is established for function fields over an algebraically closed field.     

Higher-dimensional voronoi diagrams in linear expected time

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ∵(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ∵(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense. Based upon work supported by the National Science Foundation under Grant No. CCR-8658139 while the author was a student at Carnegie-Mellon University.     

ADDITIVE FAMILIES OF INVARIANTS OF SKEWSYMMETRIC TENSORS

Abstract

Let d be a positive integer and F be a field of characteristic 0. Suppose that for each positive integer n, I _n is a polynomial invariant of the usual action of GL_n (F) on Λ^d(Fⁿ), such that for t ? Λ^d(F ^k) and s ? Λ^d(F ^l), I _{k + l} (t l s) = I _k(t)I _t (s), where t ⊥ s is defined in §1.4. Then we say that {I_n} is an additive family of invariants of the skewsymmetric tensors of degree d, or, briefly, an additive family of invariants. If not all the I_n are constant we say that the family is non-trivial. We show that in each even degree d there is a non-trivial additive family of invariants, but that this is not so for any odd d. These results are analogous to those in our paper [3] for symmetric tensors. Our proofs rely on the symbolic method for representing invariants of skewsymmetric tensors. To keep this paper self-contained we expound some of that theory, but for the proofs we refer to the book [2] of Grosshans, Rota and Stein.     

[a,b]-factorization of a graph

Let a and b be integers such that 0 ? a ? b. Then a graph G is called an [a, b]-graph if a ? d_G(x) ? b for every x ? V(G), and an [a, b]-factor of a graph is defined to be its spanning subgraph F such that a ? d_F(x) ? b for every vertex x, where d_G(x) and d_F(x) denote the degrees of x in G and F, respectively. If the edges of a graph can be decomposed into [a.b]-factors then we say that the graph is [2a, 2a]-factorable. We prove the following two theorems: (i) a graph G is [2a, 2b)-factorable if and only if G is a [2am,2bm]-graph for some integer m, and (ii) every [8m + 2k, 10m + 2k]-graph is [1,2]-factorable.     

The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

Representations of algebraic groups over a 2-dimensional local field

We introduce a categorical framework for the study of representations of G(F), where G is a reductive group, and F is a 2-dimensional local field, i.e. F = K((t)), where K is a local field. Our main result says that the space of functions on G(F), which is an object of a suitable category of representations of G(F) with the respect to the action of G on itself by left translations, becomes a representation of a certain central extension of G(F), when we consider the action by right translations.     

One-Sided Ideal Growth of Free Associative Algebras

Let R be a finitely generated associative algebra with unity over a finite field \Bbb F_q{\Bbb F}_q . Denote by a _n (R) the number of left ideals J ⊂ R such that dim R/J = n for all n ≥ 1. We explicitly compute and find asymptotics of the left ideal growth for the free associative algebra A _d of rank d with unity over \Bbb F_q{\Bbb F}_q , where d ≥ 1. This function yields a bound a _n (R) ≤ a _n (A _d ), n ? \Bbb Nn\in{\Bbb N} , where R is an arbitrary algebra generated by d elements. Denote by m _n (R) the number of maximal left ideals J ⊂ R such that dim R/J = n, for n ≥ 1. Let d ≥ 2, we prove that m _n (A _d ) ≈ a _n (A _d ) as n → ∞.     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

Formes homogènes de degré 3 et puissances p-ièmes

In this paper, we are interested in diophantine equations of type F(x,y)=dzp where F is a separable homogeneous form of degree ?3 with integer coefficients, d a fixed integer ?1 and p a prime number ?7. As a consequence of the abc conjecture, if p is sufficiently large and (a,b,c) is a nontrivial proper solution of the above equation, we have c=±1. In the case where F has degree 3, we associate to (a,b,c) an elliptic curve defined over Q called the Frey curve or Hellegouarch-Frey curve. This allows us to deduce our conjecture from another one about elliptic curves attributed to G. Frey and B. Mazur (which is itself a consequence of the abc conjecture). We then applied our construction to the study of an explicit form. We give some results about the set of nontrivial proper solutions of the equation considered for several values of d.     

On the log-concavity of Hilbert series of Veronese subrings and Ehrhart series

For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write ${\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}}For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write \frach(t)(1 - t)^{d + 1}=?_{m 3 0} g(m)  t^m{\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}} , for some polynomial g(m) with rational coefficients, then \fracU_nh(t)(1- t)^d+1 = ?_{m 3 0}g(nm)  t^m{\frac{{\rm{U}}_{n}h(t)}{(1- t)^{d+1}} = \sum_{m \geq 0}g(nm) \, t^{m}} . We show that there exists a positive integer n _d , depending only on d, such that if h(t) is a polynomial of degree at most d with nonnegative integer coefficients and h(0) = 1, then for n ≥ n _d , U _n h(t) has simple, real, negative roots and positive, strictly log concave and strictly unimodal coefficients. Applications are given to Ehrhart δ-polynomials and unimodular triangulations of dilations of lattice polytopes, as well as Hilbert series of Veronese subrings of Cohen–Macauley graded rings.     

On the geometry of random Cantor sets and fractal percolation

Random Cantor sets are constructions which generalize the classical Cantor set, middle third deletion being replaced by a random substitution in an arbitrary number of dimensions. Two results are presented here. (a) We establish a necessary and sufficient condition for the projection of ad-dimensional random Cantor set in [0,1]^d onto ane-dimensional coordinate subspace to contain ane-dimensional ball with positive probability. The same condition applies to the event that the projection is the entiree-dimensional unit cube [0,1] ^e . This answers a question of Dekking and Meester,⁽⁹⁾ (b) The special case of fractal percolation arises when the substitution is as follows: The cube [0,1] ^d is divided intoM ^d subcubes of side-lengthM ^–, and each such cube is retained with probabilityp independently of all other subcubes. We show that the critical valuep _c(M, d) ofp, marking the existence of crossings of [0,1] ^d contained in the limit set, satisfiesp _c(M, d)p _c(d) asM, wherep _c(d) is the critical probability of site percolation on a latticeL ^d obtained by adding certain edges to the hypercubic lattice ^d . This result generalizes in an unexpected way a finding of Chayes and Chayes,⁽⁴⁾ who studied the special case whend=2.     

On the vanishing of subspaces of alternating bilinear forms

Given a field F and integer n≥3, we introduce an invariant s_n (F) which is defined by examining the vanishing of subspaces of alternating bilinear forms on 2-dimensional subspaces of vector spaces. This invariant arises when we calculate the largest dimension of a subspace of n?×?n skew-symmetric matrices over F which contains no elements of rank 2. We show how to calculate s_n (F) for various families of field F, including finite fields. We also prove the existence of large subgroups of the commutator subgroup of certain p-groups of class 2 which contain no non-identity commutators.