On the genericity of maximum rank distance and Gabidulin codes

We consider linear rank-metric codes in \({\mathbb {F}}_{q^m}^n\). We show that the properties of being maximum rank distance (MRD) and non-Gabidulin are generic over the algebraic closure of the underlying field, which implies that over a large extension field a randomly chosen generator matrix generates an MRD and a non-Gabidulin code with high probability. Moreover, we give upper bounds on the respective probabilities in dependence on the extension degree m.     

Sharp bounds for integral means

We introduce a bound M of f, ‖f‖_∞?M?2‖f‖_∞, which allows us to give for 0?p<∞ sharp upper bounds, and for −∞<p<0 sharp lower bounds for the average of |f|^p over E if the average of f over E is zero. As an application we give a new proof of Grüss's inequality estimating the covariance of two random variables. We also give a new estimate for the error term in the trapezoidal rule.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

Delta sets for divisors supported in two points

In Duursma and Park (2010) [7], the authors formulate new coset bounds for algebraic geometric codes. The bounds give improved lower bounds for the minimum distance of algebraic geometric codes as well as improved thresholds for algebraic geometric linear secret sharing schemes. The bounds depend on the delta set of a coset and on the choice of a sequence of divisors inside the delta set. In this paper we give general properties of delta sets and we analyze sequences of divisors supported in two points on Hermitian and Suzuki curves.     

Bounds on Laplacian eigenvalues related to total and signed domination of graphs

A total dominating set in a graph G is a subset X of V (G) such that each vertex of V (G) is adjacent to at least one vertex of X. The total domination number of G is the minimum cardinality of a total dominating set. A function f: V (G) → {−1, 1} is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of G is the minimum weight of an SDF on G. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.     

A geometric approach to divergent points of higher dimensional Collatz mappings

We define generalized Collatz mappings on free abelian groups of finite rank and study their iteration trajectories. Using geometric arguments we describe cones of points having a divergent trajectory and we deduce lower bounds for the density of the set of divergent points. As an application we give examples which show that the iteration of generalized Collatz mappings on rings of algebraic integers can behave quite differently from the conjectured behavior in \(\mathbb {Z}\).     

Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem

This paper presents several methodological and algorithmic improvements over a state-of-the-art dynamic programming algorithm for solving the bi-objective {0,1} knapsack problem. The variants proposed make use of new definitions of lower and upper bounds, which allow a large number of states to be discarded. The computation of these bounds are based on the application of dichotomic search, definition of new bound sets, and bi-objective simplex algorithms to solve the relaxed problem. Although these new techniques are not of a common application for dynamic programming, we show that the best variants tested in this work can lead to an average improvement of 10 to 30 % in CPU-time and significant less memory usage than the original approach in a wide benchmark set of instances, even for the most difficult ones in the literature.     

强混合误差回归函数小波估计的Berry-Esseen界

设回归模型 Y_ni=g(t_ni)+ε_ni, i =1,…, n, 其中{t_ni} 为固定设计点列, g(?) 是定义在[0,1]上的未知函数, {ε_ni}为随机误差. 该文主要讨论了误差为强混合序列情形下, 回归函数g(?)小波估计的Berry-Esseen 界, 其界可达 O(n-^1/6).     

Constructions and bounds on linear error-block codes

We obtain new bounds on the parameters and we give new constructions of linear error-block codes. We obtain a Gilbert–Varshamov type construction. Using our bounds and constructions we obtain some infinite families of optimal linear error-block codes over . We also study the asymptotic of linear error-block codes. We define the real valued function α _q,m,a (δ), which is an analog of the important real valued function α _q (δ) in the asymptotic theory of classical linear error-correcting codes. We obtain both Gilbert–Varshamov and algebraic geometry type lower bounds on α _q,m,a (δ). We compare these lower bounds in graphs.      

The Return of the Baer Subplane

We discuss the notion of a tangency set in a projective plane, generalising the well-studied idea of a minimal blocking set. Tangency sets have recently been used in connection with the coding theory related to algebraic curves over finite fields, and they are closely related to the strong representative systems introduced by T. Illés, T. Szonyi, and F. Wettl (1991,Mitt. Math. Sem. Giessen201, 97–107). Here we give bounds on the possible sizes of tangency sets, and structural results are obtained in the extremal cases.     

Une majoration de la multiplicité spectrale d'opérateurs associés à des cocycles réguliers

We study the spectral multiplicity of unitary operators of defined by cocycles over an irrational rotation α. We prove that the multiplicity is finite whenever the cocycle has bounded variation and we give explicit bounds. For a cocycle given by an absolutely continuous function ϕ on [0,1], we show that the multiplicity is strictly less than max (2.•∫ϕ(x)dx•+1), which is optimal in the case ϕ(x)=nx (where the multiplicity is exactlyn). The proofs are based on the representation of the rotation as a “local rank one” transformation, which arises from the continued fraction expansion of α.      

On the Solutions of a Singular Nonlinear Periodic Boundary Value Problem

In this paper, we consider the following singular nonlinear problem

Polynomials with bounds and numerical approximation

We discuss the generation of polynomials with two bounds —an upper bound and a lower bound— on compact sets \(\mathcal C=[0,1]^{d}\subset \mathbb {R}^{d}\) in view on numerical approximation and scientific computing. The presentation is restricted to d = 1,2. We show that a composition formula based on a weighted 4-squares Euler identity generates all such polynomials in dimension d=1. It yields a new algebraic or compositional approach to the classical problem related to polynomials with minimal uniform norm. The theoretical generalization to the multivariate case is discussed in dimension d=2 by means of the 8-squares Degen identity and the connection with quaternions algebras is made explicit. Numerical results in dimension d=1 illustrate the potentialities of this approach and some implementation details are provided.     

On the law of the iterated logarithm for subsequences for a stable subordinator

Let {X(t): 0≤t<∞) be a stable subordinator with α∈(0,1). For increasing sequences t_k we give normalizing constants a_k such thatliminf _k→∞ a _k ⁻¹ X(t_k) is a.s constant. We also derive a.s. upper bounds. Proceedings of the XVI Seminar on Stability Problems for Stochastic Models Part I, Eger, Hungary, 1994.     

On multiplicative independence of rational function iterates

We give lower bounds for the degree of multiplicative combinations of iterates of rational functions (with certain exceptions) over a general field, establishing the multiplicative independence of said iterates. This leads to a generalisation of Gao’s method for constructing elements in the finite field $${\mathbb {F}}_{q^n}$$ whose orders are larger than any polynomial in n when n becomes large. Additionally, we discuss the finiteness of polynomials which translate a given finite set of polynomials to become multiplicatively dependent.     

Fractional set systems with few disjoint pairs

Ahlswede (1980) [1] and Frankl (1977) [5] independently found a result about the structure of set systems with few disjoint pairs. Bollobás and Leader (2003) [3] gave an alternate proof by generalizing to fractional set systems and noting that the optimal fractional set systems are {0,1}-valued. In this paper we show that this technique does not extend to t-intersecting families. We find optimal fractional set systems for some infinite classes of parameters, and we point out that they are strictly better than the corresponding {0,1}-valued fractional set systems. We prove some results about the structure of an optimal fractional set system, which we use to produce an algorithm for finding such systems. The run time of the algorithm is polynomial in the size of the ground set.     

q-Functions and extreme topological measures

q-Functions provide a method for constructing topological measures. We give necessary and sufficient conditions for a composition of a q-function and a topological measure to be a topological measure. Regular and extreme step q-functions are characterized by certain regions in Rn. Then extreme q-functions are used to study extreme topological measures. For example, we prove (under some assumptions on the underlying set) that given n, there are different types of extreme topological measures with values 0,1/n,…,1. In contrast, in the case of measures the only extreme points are {0,1}-valued, i.e., point masses.     

Teichmüller curves in genus three and just likely intersections in $\mathbf{G}_{m}^{n}\times\mathbf{G}_{a}^{n}$

We prove that the moduli space of compact genus three Riemann surfaces contains only finitely many algebraically primitive Teichmüller curves. For the stratum \(\Omega\mathcal{M}_{3}(4)\), consisting of holomorphic one-forms with a single zero, our approach to finiteness uses the Harder-Narasimhan filtration of the Hodge bundle over a Teichmüller curve to obtain new information on the locations of the zeros of eigenforms. By passing to the boundary of moduli space, this gives explicit constraints on the cusps of Teichmüller curves in terms of cross-ratios of six points on \(\mathbf{P}^{1}\).These constraints are akin to those that appear in Zilber and Pink’s conjectures on unlikely intersections in diophantine geometry. However, in our case one is lead naturally to the intersection of a surface with a family of codimension two algebraic subgroups of \(\mathbf{G}_{m}^{n}\times\mathbf{G}_{a}^{n}\) (rather than the more standard \(\mathbf{G}_{m}^{n}\)). The ambient algebraic group lies outside the scope of Zilber’s Conjecture but we are nonetheless able to prove a sufficiently strong height bound.For the generic stratum \(\Omega\mathcal{M}_{3}(1,1,1,1)\), we obtain global torsion order bounds through a computer search for subtori of a codimension-two subvariety of \(\mathbf{G}_{m}^{9}\). These torsion bounds together with new bounds for the moduli of horizontal cylinders in terms of torsion orders yields finiteness in this stratum. The intermediate strata are handled with a mix of these techniques.