Episciences.org
Not a member yet
6707 research outputs found
Sort by
Linear Hashing with guarantees and two-sided Kakeya bounds
No full textWe show that a randomly chosen linear map over a finite field gives a goodhash function in the sense. More concretely, consider a set and a randomly chosen linear map with taken to be sufficiently smaller than .Let denote a random variable distributed uniformly on . Our maintheorem shows that, with high probability over the choice of , the randomvariable is close to uniform in the norm. In otherwords, {\em every} element in the range has about the samenumber of elements in mapped to it. This complements the widely-usedLeftover Hash Lemma (LHL) which proves the analog statement under thestatistical, or , distance (for a richer class of functions) as well asprior work on the expected largest 'bucket size' in linear hash functions[ADMPT99]. By known bounds from the load balancing literature [RS98], ourresults are tight and show that linear functions hash as well as trully randomfunction up to a constant factor in the entropy loss. Our proof leverages aconnection between linear hashing and the finite field Kakeya problem andextends some of the tools developed in this area, in particular the polynomialmethod.Comment: Journal Version for TheoretiCS. Added Theorem 3.4 which gives more flexible field size requirements for finding balanced subspace
The universal vector extension of an abeloid variety
No full textLet be an abelian variety over a complete non-Archimedean field . Theuniversal cover of the Berkovich space attached to reflects the reductionbehaviour of . In this paper the universal cover of the universal vectorextension of is described. In a forthcoming paper (arXiv:2007.04659), this will be one of the crucial tools to show that rigidanalytic functions on are all constant.Comment: This is the first part of arXiv:2007.04659 which is now split into tw
André Rouchier : d’un siècle à l’autre, le projet demeure
No full textHommage à André Rouchier, professeur en formation des maitres à l’IUFM, spécialiste de didactique des mathématiques et fondateur de la revue Recherches en didactique des mathématiques (RDM)
Bijective proof of a conjecture on unit interval posets
No full textIn a recent preprint, Matherne, Morales and Selover conjectured that twodifferent representations of unit interval posets are related by the famouszeta map in -Catalan combinatorics. This conjecture was proved recently byG\'elinas, Segovia and Thomas using induction. In this short note, we provide abijective proof of the same conjecture with a reformulation of the zeta mapusing left-aligned colored trees, first proposed in the study of parabolicTamari lattices.Comment: 8 pages, 3 figures. Accepted by Discrete Mathematics & Theoretical Computer Scienc
A generalization of a fourth irreducibility theorem of I. Schur
No full textIn 1929, Issai Schur investigated the irreducibility over the rationals of a few different polynomials. Generalizations of all but one were previously given in the literature, and this paper establishes a more general result of the last one
Algebraic entropy for systems of quad equations
No full textIn this work I discuss briefly the calculation of the algebraic entropy forsystems of quad equations. In particular, I observe that since systems ofmultilinear equations can have algebraic solution, in some cases one might needto restrict the direction of evolution only to the pair of vertices yielding abirational evolution. Some examples from the exiting literature are presentedand discussed within this framework.Comment: 24 pages (amsart style), 5 figures. This paper is dedicated to the memory of Prof. Decio Lev
Cohomology classes of complex approximable algebras
No full textHuayi Chen introduces the notion of an approximable graded algebra, which heuses to prove a Fujita-type theorem in the arithmetic setting, and asked if anysuch algebra is the graded ring of a big line bundle on a projective variety.This was proved to be false in a previous paper of the author's, whosubsequently proved that any such algebra is associated to an infinite Weildivisor. In this paper, we show that over the complex numbers, this infiniteWeil divisor necessarily has finite cohomology class.Comment: 8 pages. arXiv admin note: text overlap with arXiv:1709.06945 Minor revisio
Galois connecting call-by-value and call-by-name
No full textWe establish a general framework for reasoning about the relationship betweencall-by-value and call-by-name. In languages with computational effects, call-by-value and call-by-nameexecutions of programs often have different, but related, observablebehaviours. For example, if a program might diverge but otherwise has noeffects, then whenever it terminates under call-by-value, it terminates withthe same result under call-by-name. We propose a technique for stating andproving properties like these. The key ingredient is Levy's call-by-push-valuecalculus, which we use as a framework for reasoning about evaluation orders. Weshow that the call-by-value and call-by-name translations of expressions intocall-by-push-value have related observable behaviour under certain conditionson computational effects, which we identify. We then use this fact to constructmaps between the call-by-value and call-by-name interpretations of types, andidentify further properties of effects that imply these maps form a Galoisconnection. These properties hold for some computational effects (such asdivergence), but not others (such as mutable state). This gives rise to ageneral reasoning principle that relates call-by-value and call-by-name. Weapply the reasoning principle to example computational effects includingdivergence and nondeterminism
An exercise in experimental mathematics: calculation of the algebraic entropy of a map
No full textWe illustrate the use of the notion of derived recurrences introduced earlierto evaluate the algebraic entropy of self-maps of projective spaces. We inparticular give an example, where a complete proof is still awaited, but wheredifferent approaches are in such perfect agreement that we can trust we get toan exact result. This is an instructive example of experimental mathematics.Comment: Version formatted for Open Communication in Nonlinear Physics (OCNMP) Special issue in Memory of Professor Decio Lev
Soliton equations: admitted solutions and invariances via B\"acklund transformations
No full textA couple of applications of B\"acklund transformations in the study ofnonlinear evolution equations is here given. Specifically, we are concernedabout third order nonlinear evolution equations. Our attention is focussed onone side, on proving a new invariance admitted by a third order nonlinearevolution equation and, on the other one, on the construction of solutions.Indeed, via B\"acklund transformations, a {\it B\"acklund chart}, connectingAbelian as well as non Abelian equations can be constructed. The importance ofsuch a net of links is twofold since it indicates invariances as well as allowsto construct solutions admitted by the nonlinear evolution equations itrelates. The present study refers to third order nonlinear evolution equationsof KdV type. On the basis of the Abelian wide B\"acklund chart which connects various different third order nonlinearevolution equations an invariance admitted by the {\it Korteweg-deVries interacting soliton}(int.sol.KdV) equation is obtained and a related new explicit solution isconstructed. Then, the corresponding non-Abelian {\it B\"acklund chart}, shows how to construct matrix solutions of the mKdV equations: some recently obtainedsolutions are reconsidered.Comment: 11 pages, 6 figures. arXiv admin note: text overlap with arXiv:2101.0924