Search Results

You are looking at 1 - 10 of 11 items for

  • Author or Editor: András Sárközy x
  • Refine by Access: All Content x
Clear All Modify Search

In a series of papers Mauduit and Sárközy studied finite pseudorandom sequences. In particular, in Part I they showed that the Legendre symbol forms an 'ideally good' pseudorandom sequence. In other parts of the series numerous other binary sequences have been tested for pseudorandomness but neither of them proved to be as 'good' as the Legendre symbol. Here another 'very good' sequence is constructed by using the notion of index.

Restricted access

Summary  

Recently, Goubin, Mauduit, Rivat and Srkzy have given three constructions for large families of binary sequences. In each of these constructions the sequence is defined by modulo \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $p$ \end{document} congruences where \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $p$ \end{document} is a prime number. In this paper the three constructions are extended to the case when the modulus is of the form \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $pq$ \end{document} where \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $p$ \end{document} , \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $q$ \end{document} are two distinct primes not far apart (note that the well-known Blum-Blum-Shub and RSA constructions for pseudorandom sequences are also of this type). It is shown that these modulo \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $pq$ \end{document} constructions also have certain strong pseudorandom properties but, e.g., the (``long range'') correlation of order \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $4$ \end{document} is large (similar phenomenon may occur in other modulo \documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $pq$ \end{document} constructions as well).

Restricted access

Abstract  

The pseudorandom properties of finite binary sequences have been studied recently intensively. In the papers written on this subject the two distinct elements of the sequences are chosen equally with probability 1/2. In this paper the authors extend the work to the more general case when the two elements are chosen with probability p, resp. 1-p.

Restricted access

Summary By using the multiplicative inverse modulo p, a large family of finite binary sequences is constructed with strong pseudorandom properties. The crucial tool in the proofs is an (additive) character sum estimate of Eichenauer--Hermann and Niederreiter.

Restricted access
Restricted access

Summary  

It is proved that the summands of almost all unequal partitions of nare well-distributed modulo dfor d=o(n 1/2).

Restricted access
Restricted access

A proper edge coloring of a graph 𝐺 is strong if the union of any two color classes does not contain a path with three edges (i.e. the color classes are induced matchings). The strong chromatic index 𝑞(𝐺) is the smallest number of colors needed for a strong coloring of 𝐺. One form of the famous (6, 3)-theorem of Ruzsa and Szemerédi (solving the (6, 3)-conjecture of Brown–Erdős–Sós) states that 𝑞(𝐺) cannot be linear in 𝑛 for a graph 𝐺 with 𝑛 vertices and 𝑐𝑛2 edges. Here we study two refinements of 𝑞(𝐺) arising from the analogous (7, 4)-conjecture. The first is 𝑞𝐴(𝐺), the smallest number of colors needed for a proper edge coloring of 𝐺 such that the union of any two color classes does not contain a path or cycle with four edges, we call it an A-coloring. The second is 𝑞𝐵(𝐺), the smallest number of colors needed for a proper edge coloring of 𝐺 such that all four-cycles are colored with four different colors, we call it a B-coloring. These notions lead to two stronger and one equivalent form of the (7, 4)-conjecture in terms of 𝑞𝐴(𝐺), 𝑞𝐵(𝐺) where 𝐺 is a balanced bipartite graph. Since these are questions about graphs, perhaps they will be easier to handle than the original special(7, 4)-conjecture. In order to understand the behavior of 𝑞𝐴(𝐺) and 𝑞𝐵(𝐺), we study these parameters for some graphs.

We note that 𝑞𝐴(𝐺) has already been extensively studied from various motivations. However, as far as we know the behavior of 𝑞𝐵(𝐺) is studied here for the first time.

Open access