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.      

Compact and Loeb Hausdorff spaces in \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {ZF}$\end{document} and the axiom of choice for families of finite sets

Given a set X, $\mathsf {AC}^{\mathrm{fin}(X)}$ denotes the statement: “$[X]^{<\omega }\backslash \lbrace \varnothing \rbrace$ has a choice set” and $\mathcal {C}_\mathrm{R}\big (\mathbf {2}^{X}\big )$ denotes the family of all closed subsets of the topological space $\mathbf {2}^{X}$ whose definition depends on a finite subset of X. We study the interrelations between the statements $\mathsf {AC}^{\mathrm{fin}(X)},$ $\mathsf {AC}^{\mathrm{fin}([X]^{<\omega })},$ $\mathsf {AC}^{\mathrm{fin} (F_{n}(X,2))},$ $\mathsf {AC}^{\mathrm{fin}(\mathcal {\wp }(X))}$ and “$\mathcal {C}_\mathrm{R}\big (\mathbf {2}^{X}\big )\backslash \lbrace \varnothing \rbrace$has a choice set”. We show:

• (i) $\mathsf {AC}^{\mathrm{fin}(X)}$ iff $\mathsf {AC}^{\mathrm{fin}([X]^{<\omega } )}$ iff $\mathcal {C}_\mathrm{R}\big (\mathbf {2}^{X}\big )\backslash \lbrace \varnothing \rbrace$ has a choice set iff $\mathsf {AC}^{\mathrm{fin}(F_{n}(X,2))}$.
• (ii) $\mathsf {AC}_{\mathrm{fin}}$ ($\mathsf {AC}$ restricted to families of finite sets) iff for every set X, $\mathcal {C}_\mathrm{R}\big (\mathbf {2}^{X}\big )\backslash \lbrace \varnothing \rbrace$ has a choice set.
• (iii) $\mathsf {AC}_{\mathrm{fin}}$ does not imply “$\mathcal {K}\big (\mathbf {2}^{X}\big )\backslash \lbrace \varnothing \rbrace$ has a choice set($\mathcal {K}(\mathbf {X})$ is the family of all closed subsets of the space $\mathbf {X}$)
• (iv) $\mathcal {K}(\mathbf {2}^{X})\backslash \lbrace \varnothing \rbrace$ implies $\mathsf {AC}^{\mathrm{fin}(\mathcal {\wp }(X))}$ but $\mathsf {AC}^{\mathrm{fin}(X)}$ does not imply $\mathsf {AC}^{\mathrm{fin}(\mathcal {\wp }(X))}$.

We also show that “For every setX, “$\mathcal {K}\big (\mathbf {2}^{X}\big )\backslash \lbrace \varnothing \rbrace$has a choice set” iff “for every setX, $\mathcal {K}\big (\mathbf {[0,1]}^{X}\big )\backslash \lbrace \varnothing \rbrace$has a choice set” iff “for every product$\mathbf {X}$of finite discrete spaces,$\mathcal {K}(\mathbf {X})\backslash \lbrace \varnothing \rbrace$ has a choice set”.     

Distribution of values of bounded generalized polynomials

A generalized polynomial is a real-valued function which is obtained from conventional polynomials by the use of the operations of addition, multiplication, and taking the integer part; a generalized polynomial mapping is a vector-valued mapping whose coordinates are generalized polynomials. We show that any bounded generalized polynomial mapping u: Z ^d  → R ^l has a representation u(n) = f(ϕ(n)x), n ∈ Z ^d , where f is a piecewise polynomial function on a compact nilmanifold X, x ∈ X, and ϕ is an ergodic Z ^d -action by translations on X. This fact is used to show that the sequence u(n), n ∈ Z ^d , is well distributed on a piecewise polynomial surface (with respect to the Borel measure on that is the image of the Lebesgue measure under the piecewise polynomial function defining ). As corollaries we also obtain a von Neumann-type ergodic theorem along generalized polynomials and a result on Diophantine approximations extending the work of van der Corput and of Furstenberg–Weiss.     

On the Number of Topological Types Occurring in a Parameterized Family of Arrangements

Let be an o-minimal structure over ℝ, a closed definable set, and

An algorithm for semi-infinite polynomial optimization

We consider the semi-infinite optimization problem:

Around splitting and reaping for partitions of ω

We investigate splitting number and reaping number for the structure (ω) ^ω of infinite partitions of ω. We prove that \mathfrakr_d ￡ non(M),non(N),\mathfrakd{\mathfrak{r}_{d}\leq\mathsf{non}(\mathcal{M}),\mathsf{non}(\mathcal{N}),\mathfrak{d}} and \mathfraks_d 3 \mathfrakb{\mathfrak{s}_{d}\geq\mathfrak{b}} . We also show the consistency results ${\mathfrak{r}_{d} > \mathfrak{b}, \mathfrak{s}_{d} < \mathfrak{d}, \mathfrak{s}_{d} < \mathfrak{r}, \mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})}${\mathfrak{r}_{d} > \mathfrak{b}, \mathfrak{s}_{d} < \mathfrak{d}, \mathfrak{s}_{d} < \mathfrak{r}, \mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})} and ${\mathfrak{s}_{d} > \mathsf{cof}(\mathcal{M})}${\mathfrak{s}_{d} > \mathsf{cof}(\mathcal{M})} . To prove the consistency \mathfrakr_d < add(M){\mathfrak{r}_{d} < \mathsf{add}(\mathcal{M})} and \mathfraks_d < cof(M){\mathfrak{s}_{d} < \mathsf{cof}(\mathcal{M})} we introduce new cardinal invariants \mathfrakr_pair{\mathfrak{r}_{pair}} and \mathfraks_pair{\mathfrak{s}_{pair}} . We also study the relation between \mathfrakr_pair, \mathfraks_pair{\mathfrak{r}_{pair}, \mathfrak{s}_{pair}} and other cardinal invariants. We show that cov(M),cov(N) ￡ \mathfrakr_pair ￡ \mathfraks_d,\mathfrakr{\mathsf{cov}(\mathcal{M}),\mathsf{cov}(\mathcal{N})\leq\mathfrak{r}_{pair}\leq\mathfrak{s}_{d},\mathfrak{r}} and \mathfraks ￡ \mathfraks_pair ￡ non(M),non(N){\mathfrak{s}\leq\mathfrak{s}_{pair}\leq\mathsf{non}(\mathcal{M}),\mathsf{non}(\mathcal{N})} .     

Quadratic Gröbner bases for smooth 3×3 transportation polytopes

The toric ideals of 3×3 transportation polytopes T_rc\mathsf{T}_{\mathbf{rc}} are quadratically generated. The only exception is the Birkhoff polytope B ₃. If T_rc\mathsf{T}_{\mathbf{rc}} is not a multiple of B ₃, these ideals even have square-free quadratic initial ideals. This class contains all smooth 3×3 transportation polytopes.     

On Convergence and Convolutions of Random Signed Measures

Let μ _n be a sequence of random finite signed measures on the locally compact group G equal to either or ℝ ^d . We give weak conditions on the sequence μ _n and on functions K such that the convolution product μ _n *K, and its derivatives, converge in law, in probability, or almost surely in the Banach spaces or L ^p (G). Examples for sequences μ _n covered are the empirical process (possibly arising from dependent data) and also random signed measures where is some (nonparametric) estimator for the measure ℙ, including the usual kernel and wavelet based density estimators with MISE-optimal bandwidths. As a statistical application, we apply the results to study convolutions of density estimators.      

Hölder Continuity of Random Processes

For a Young function φ and a Borel probability measure m on a compact metric space (T,d) the minorizing metric is defined by

Absolute continuity and singularity of Palm measures of the Ginibre point process

We prove a dichotomy between absolute continuity and singularity of the Ginibre point process \(\mathsf {G}\) and its reduced Palm measures \(\{\mathsf {G}_{\mathbf {x}}, \mathbf {x} \in \mathbb {C}^{\ell }, \ell = 0,1,2\ldots \}\), namely, reduced Palm measures \(\mathsf {G}_{\mathbf {x}}\) and \(\mathsf {G}_{\mathbf {y}}\) for \(\mathbf {x} \in \mathbb {C}^{\ell }\) and \(\mathbf {y} \in \mathbb {C}^{n}\) are mutually absolutely continuous if and only if \(\ell = n\); they are singular each other if and only if \(\ell \not = n\). Furthermore, we give an explicit expression of the Radon–Nikodym density \(d\mathsf {G}_{\mathbf {x}}/d \mathsf {G}_{\mathbf {y}}\) for \(\mathbf {x}, \mathbf {y} \in \mathbb {C}^{\ell }\).     

Map Preserving Local Properties of a Digital Image

In order to study digital topological properties of a k-surface in Z ⁿ , we generalize the topological number in Bertrand (Pattern Recogn. Lett. 15:1003–1011, 1994). Furthermore, we show that a local (k ₀,k ₁)-isomorphism preserves some digital-topological properties, such as a generalized topological number and a simple k ₀-point, and prove that a local (k ₀,k ₁)-isomorphism takes a simple k ₀-surface in into a simple k ₁-surface in .      

On the fourier coefficients of functions concentrated on a subset of the circle

We consider ,mE > 0,G(E) is a certain subspace of L ¹ (E) consisting of functions concentrated on E and integrable, and {d_k}, (k ∈ ℤ) in a summable sequence of positive numbers. It is proved that if G(E)=L^p(E), p≥2, then there exists f∈G(E) such that |f(n)|≥d_n, (one of the questions involved in the majorization problem). Sufficient conditions are obtained for certain other function classes G(E). We study the question of partial majorization. Bibliography: 2 titles. Translated fromProblemy Matematicheskogo Analiza, No. 13, 1992, pp. 42–48.     

Complexes of Graphs with Bounded Matching Size

For positive integers k,n, we investigate the simplicial complex of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r,s and k the simplicial complex of all bipartite graphs G on bipartition such that there is no matching of size k in G, and obtain results similar to those obtained for . S. Linusson and V. Welker supported by EC’s IHRP program through grant HPRN-CT-2001-00272. J. Shareshian partially supported by National Science Foundation grants DMS-0070757 and DMS-0030483.     

Equivariant vector bundles on Drinfeld’s upper half space

Let be Drinfeld’s upper half space over a finite extension K of ℚ _p . We construct for every GL _d+1-equivariant vector bundle on ℙ ^d _K , a GL _d+1(K)-equivariant filtration by closed subspaces on the K-Fréchet . This gives rise by duality to a filtration by locally analytic GL _d+1(K)-representations on the strong dual . The graded pieces of this filtration are locally analytic induced representations from locally algebraic ones with respect to maximal parabolic subgroups. This paper generalizes the cases of the canonical bundle due to Schneider and Teitelbaum [ST1] and that of the structure sheaf by Pohlkamp [P].     

Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

Bispectral and (\mathfrak{gl}_{N},\mathfrak{gl}_{M}) dualities

Let be a space of quasipolynomials of dimension N=N ₁+⋅⋅⋅+N _n . We define the regularized fundamental operator of V as the polynomial differential operator D=∑ _i=0 ^N A _N−i (x)∂ _x ⁱ annihilating V and such that its leading coefficient A ₀ is a polynomial of the minimal possible degree. We apply a suitable integral transformation to V to construct a space of quasipolynomials whose regularized fundamental operator is the differential operator ∑ _i=0 ^N u ⁱ A _N−i (∂ _u ). Our integral transformation corresponds to the bispectral involution on the space of rational solutions (vanishing at infinity) of the KP hierarchy. As a corollary of the properties of the integral transformation, we obtain a correspondence between critical points of the two master functions associated with the -dual Gaudin models and also between the corresponding Bethe vectors. The research of E. M. was supported in part by the NSF (Grant No. DMS-0140460). The research of A. V. was supported in part by the NSF (Grant No. DMS-0244579).     

Fast convolutions meet Montgomery

Arithmetic in large ring and field extensions is an important problem of symbolic computation, and it consists essentially of the combination of one multiplication and one division in the underlying ring. Methods are known for replacing one division by two short multiplications in the underlying ring, which can be performed essentially by using convolutions.

However, while using school-book multiplication, modular multiplication may be grouped into operations (where denotes the number of operations of one multiplication in the underlying ring), the short multiplication problem is an important obstruction to convolution. It raises the costs in that case to . In this paper we give a method for understanding and bypassing this problem, thus reducing the costs of ring arithmetic to roughly when also using fast convolutions. The algorithms have been implemented with results which fit well the theoretical prediction and which shall be presented in a separate paper.

     

A general class of inequalities with mixed means

Suppose (T, Σ, μ) is a space with positive measure,f: ? → ? is a strictly monotone continuous function, and &;(T) is the set of real μ-measurable functions onT. Letx(·) ∈ &;(T) andf ○x)(·) ∈L ₁(T,μ). Comparison theorems are proved for the means $\mathfrak{M}_{(T,{\mathbf{ }}\mu ,{\mathbf{ }}f)} (x( \cdot ))$ and the mixed means $\mathfrak{M}_{(T_1 ,{\mathbf{ }}\mu _1 ,{\mathbf{ }}f_1 )} (\mathfrak{M}_{(T_2 ,{\mathbf{ }}\mu _2 ,{\mathbf{ }}f_2 )} (x( \cdot )))$ these inequalities imply analogs and generalizations of some classical inequalities, namely those of Hölder, Minkowski, Bellman, Pearson, Godunova and Levin, Steffensen, Marshall and Olkin, and others. These results are a continuation of the author's studies.     

Dedekind–MacNeille Completion of n-ordered Sets

A completion of an n-ordered set is defined, by analogy with the case of posets (2-ordered sets), as a pair , where Q is a complete n-lattice and is an n-order embedding. The Basic Theorem of Polyadic Concept Analysis is exploited to construct a completion of an arbitrary n-ordered set. The completion reduces to the Dedekind–MacNeille completion in the dyadic case, the case of posets. A characterization theorem is provided, analogous to the well-known dyadic one, for the case of joined n-ordered sets. The condition of joinedness is trivial in the dyadic case and, therefore, this characterization theorem generalizes the uniqueness theorem for the Dedekind–MacNeille completion of an arbitrary poset.      

Certain Ergodic Properties of a Differential System on a Compact Differentiable Manifold

Let M ⁿ be an n-dimensional compact C ^∞-differentiable manifold, n ≥ 2, and let S be a C ¹-differential system on M ⁿ . The system induces a one-parameter C ¹ transformation group φ _t (−∞ < t < ∞) over M ⁿ and, thus, naturally induces a one-parameter transformation group of the tangent bundle of M ⁿ . The aim of this paper, in essence, is to study certain ergodic properties of this latter transformation group. Among various results established in the paper, we mention here only the following, which might describe quite well the nature of our study. (A) Let M be the set of regular points in M ⁿ of the differential system S. With respect to a given C ^∞ Riemannian metric of M ⁿ , we consider the bundle of all (n−2) spheres Q _x ⁿ⁻², x∈M, where Q _x ⁿ⁻² for each x consists of all unit tangent vectors of M ⁿ orthogonal to the trajectory through x. Then, the differential system S gives rise naturally to a one-parameter transformation group ψ _t ^# (−∞<t<∞) of . For an l-frame α = (u ₁, u ₂,⋯, u _l ) of M ⁿ at a point x in M, 1 ≥ l ≥ n−1, each u _i being in , we shall denote the volume of the parallelotope in the tangent space of M ⁿ at x with edges u ₁, u ₂,⋯, u _l by υ(α), and let . This is a continuous real function of t. Let