Recognition: unknown
On perfect hashing of numbers with sparse digit representation via multiplication by a constant
classification
🧮 math.NT
math.CO
keywords
sparsecasecoefficientsconstantconvolutiondigitsfixedfunctions
read the original abstract
Consider the set of vectors over a field having non-zero coefficients only in a fixed sparse set and multiplication defined by convolution, or the set of integers having non-zero digits (in some base $b$) in a fixed sparse set. We show the existence of an optimal (resp. almost-optimal in the latter case) `magic' multiplier constant that provides a perfect hash function which transfers the information from the given sparse coefficients into consecutive digits. Studying the convolution case we also obtain a result of non-degeneracy for Schur functions as polynomials in the elementary symmetric functions in positive characteristic.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.