Combinatorics Seminar
When: Sunday, March 30, 10am
Where: Schreiber 309
Speaker: Simon Litsyn, Tel Aviv University,
Title: In Search of Lost Time and Position
Abstract:
For a binary (plus/minus one) sequence, the peak sidelobe level
(PSL) is defined as the maximum, over nonzero shifts, of the
scalar product of the sequence with its aperiodically shifted
version.
Binary sequences with low PSL are of importance for synchronization
in time and determining position and distance to an object.
In theoretical physics, study of the PSL landscape was
introduced by Bernasconi via the so-called Bernasconi model, which
is fascinating for the fact of being completely deterministic, but
nevertheless having highly disordered ground states (sequences
with the lowest PSL) and thus possessing striking similarities
to the real glasses, with many features of a glass transition
exhibited.
In the talk I will survey the main open issues and report on
several new results:
- We show that the typical PSL of binary sequences is proportional
to \sqrt{n ln n}, thus improving on the best earlier known
result due to Moon and Moser and settling to the affirmative a
conjecture of Dmitriev and Jedwab;
- We show that the maximum of PSL in m-sequences is proportional
to 2^{m/2} ln m, thus disproving a long-standing conjecture of
it being 2^{m/2}.
The results are partly due to cooperation with N.Alon,
Ye.Domoshnitsky, A.Shpunt and A.Yudin.