Geodesic
Cardinality of subsets of the residue group with nonunit differences of elements
Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 111-125

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is concerned with the subsets $I\subset\left\{ {0,\;\ldots,\;d - 1} \right\}$ for which gcd$\left( {n - m,\;d} \right) \ne 1$ for any $n,\;m \in I$. Such subsets are called sets of nontrivial differences. Let $d > 1$ and ${d_1}$ be the least prime divisor of $d$. We prove that the largest cardinality of a set of nontrivial differences is $d/{d_1}$. Sets of nontrivial differences in which not all differences of elements are multiples of the same prime factor $d$ are called nonelementary. Let $t$ be the number of prime factors of $d$. We show that there are no nonelementary sets for $t \leqslant 2$. It is shown that a minimal nonelementary set may have arbitrary order in the interval $\overline {3,\;t} $. The largest cardinality of nonelementary sets is estimated from below and above.
Mots-clés : residue group
Keywords: differences of elements, nonunit elements, subset cardinality. 
P. V. Roldugin. Cardinality of subsets of the residue group with nonunit differences of elements. Diskretnaya Matematika, Tome 28 (2016) no. 3, pp. 111-125. http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/
@article{DM_2016_28_3_a7,
     author = {P. V. Roldugin},
     title = {Cardinality of subsets of the residue group with nonunit differences of elements},
     journal = {Diskretnaya Matematika},
     pages = {111--125},
     year = {2016},
     volume = {28},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/}
}
TY  - JOUR
AU  - P. V. Roldugin
TI  - Cardinality of subsets of the residue group with nonunit differences of elements
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 111
EP  - 125
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/
LA  - ru
ID  - DM_2016_28_3_a7
ER  - 
%0 Journal Article
%A P. V. Roldugin
%T Cardinality of subsets of the residue group with nonunit differences of elements
%J Diskretnaya Matematika
%D 2016
%P 111-125
%V 28
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2016_28_3_a7/
%G ru
%F DM_2016_28_3_a7

[1] Prachar K., Primzahlverteilung, Springer-Verlag, Berlin Gottingen Heidelberg, 1957 ; Prakhar K., Raspredelenie prostykh chisel, Mir, M., 1967, 513 pp. | MR | Zbl | MR

[2] Rosser J., Schoenfeld L., “Approximate formulas for some functions of prime numbers”, Ill. J. Math, 6:1 (1962), 64–94 | MR | Zbl

[3] Stinson D. R. Muir J. A., “On the low Hamming weight discrete logarithm problem for nonadjacent representations”, Appl. Alg. in Eng., Commun. and Comput., 16:6 (2006), 461–472 | DOI | MR | Zbl