A (v,Γ,λ) difference graph in an additive group G of order v is a copy of an abstract simple graph Γ with vertices in G such that the list of all possible differences between adjacent vertices covers ...every non-zero element of G exactly λ times. It is proved here that a (v,Γ,λ) difference graph cannot exist if v≡2(mod4) and Γ is Eulerian of odd size. As a consequence, we are able to exhibit infinitely many counterexamples to a recent conjecture proposed M. Buratti, A. Nakic and A. Wassermann.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
There are two construction methods of designs from <inline-formula> <tex-math notation="LaTeX">(n,m) </tex-math></inline-formula>-bent functions, known as translation and addition designs. In this ...article we analyze, which equivalence relation for Boolean bent functions, i.e. <inline-formula> <tex-math notation="LaTeX">(n,1) </tex-math></inline-formula>-bent functions, and vectorial bent functions, i.e. <inline-formula> <tex-math notation="LaTeX">(n,m) </tex-math></inline-formula>-bent functions with <inline-formula> <tex-math notation="LaTeX">2\le m\le n/2 </tex-math></inline-formula>, is coarser: extended-affine equivalence or isomorphism of associated translation and addition designs. First, we observe that similar to the Boolean bent functions, extended-affine equivalence of vectorial <inline-formula> <tex-math notation="LaTeX">(n,m) </tex-math></inline-formula>-bent functions and isomorphism of addition designs are the same concepts for all even <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">m\le n/2 </tex-math></inline-formula>. Further, we show that extended-affine inequivalent Boolean bent functions in <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> variables, whose translation designs are isomorphic, exist for all <inline-formula> <tex-math notation="LaTeX">n\ge 6 </tex-math></inline-formula>. This implies, that isomorphism of translation designs for Boolean bent functions is a coarser equivalence relation than extended-affine equivalence. However, we do not observe the same phenomenon for vectorial bent functions in a small number of variables. We classify and enumerate all vectorial bent functions in six variables and show, that in contrast to the Boolean case, one cannot exhibit isomorphic translation designs from extended-affine inequivalent vectorial <inline-formula> <tex-math notation="LaTeX">(6,m) </tex-math></inline-formula>-bent functions with <inline-formula> <tex-math notation="LaTeX">m\in \{ 2,3 \} </tex-math></inline-formula>.
This study investigated the problem of constructing almost difference sets from single and unions of cyclotomic classes of order 10 (with and without zero) of the finite field GF(q), where q is a ...prime of the form q = 10n+1 for integer n≥1 and q<1000. Using exhaustive computer searches in Python, the method computed unions of two classes up to nine cyclotomic classes. Moreover, the equivalence of the generated almost difference sets having the same parameters was determined up to complementation. Results showed that a single cyclotomic class formed an almost difference set for q = 31, 71, and 151, while including zero produced an almost difference set for q=11, 31, 71, and 151. Additionally, Paley partial difference sets were constructed from the union of five cyclotomic classes. These findings addressed gaps in the literature on cyclotomy of order 10.
There exist few examples of negative Latin square type partial difference sets (NLST PDSs) in nonabelian groups. We present a list of 176 inequivalent NLST PDSs in 48 nonisomorphic, nonabelian groups ...of order 64. These NLST PDSs form 8 nonisomorphic strongly regular graphs. These PDSs were constructed using a combination of theoretical techniques and computer search, both of which are described. The search was run exhaustively on 212/267 nonisomorphic groups of order 64.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
5.
Partial difference sets in C2n×C2n Malandro, Martin E.; Smith, Ken W.
Discrete mathematics,
April 2020, Volume:
343, Issue:
4
Journal Article
Peer reviewed
Let Gn denote the group C2n×C2n, where Ck is the cyclic group of order k. We give an algorithm for enumerating the regular nontrivial partial difference sets (PDS) in Gn. We use our algorithm to ...obtain all of these PDS in Gn for 2≤n≤9, and we obtain partial results for n=10 and n=11. Most of these PDS are new. For n≤4 we also identify group-inequivalent PDS. Our approach involves constructing tree diagrams and canonical colorings of these diagrams. Both the total number and the number of group-inequivalent PDS in Gn appear to grow super-exponentially in n. For n=9, a typical canonical coloring represents in excess of 10146 group-inequivalent PDS, and there are precisely 2520 reversible Hadamard difference sets.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
6.
On the difference set of two transductions Konstantinidis, Stavros; Moreira, Nelma; Reis, Rogério ...
Theoretical computer science,
11/2024, Volume:
1016
Journal Article
Peer reviewed
The difference set Δs,t of two (nondeterministic, in general) transducers s,t is the set of all input words for which the output sets of the two transducers are not equal. When the two transducers ...realize homomorphisms, their difference set is the complement of the well known equality set of the two homomorphisms. However, we show that transducer difference sets result in Chomsky-like classes of languages that are different than the classes resulting from equality sets. We also consider the following word problem: given transducers s,t and input w, tell whether the output sets s(w) and t(w) are different. In general the problem is PSPACE-complete, but it becomes NP-complete when at least one of the given transducers has finite outputs. We also provide a PRAX (polynomial randomized approximation) algorithm for the word problem as well as for the NFA (in)equivalence problem. Our presentation of PRAX algorithms improves the original presentation.
•The difference set of two transducers is the set of all input words for which the corresponding output sets are not equal.•We show that transducer difference sets result in language classes that are different than classes resulting from equality sets.•We also consider the following word problem: given transducers s,t and input w, tell whether s(w) and t(w) are different.•The problem is PSPACE-complete, but it becomes NP-complete when at least one of the given transducers has finite outputs.•We also provide polynomial randomized approximation (PRAX) algorithms for the word problem and for the NFA equivalence problem.•Our presentation of PRAX algorithms improves the original presentation.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Almost Difference Sets have extensive applications in coding theory and cryptography. In this study, we introduce new constructions of Almost Difference Sets derived from cyclotomic classes of order ...12 in the finite field GF(q), where q is a prime satisfying the form q=12n+1 for positive integers n ≥ 1 and q < 1000. We show that a single cyclotomic class of order 12 (with and without zero) can form an almost difference set. Additionally, we successfully construct almost difference sets using unions of cyclotomic classes of order 12, both for even and odd values of n. To accomplish this, an exhaustive computer search employing Python was conducted. The method involved computing unions of two cyclotomic classes up to eleven classes and assessing the presence of almost difference sets. Finally, we classify the resulting almost difference sets with the same parameters up to equivalence and complementation.
We study finite groups
G
having a subgroup
H
and
D
⊂
G
\
H
such that (i) the multiset
{
x
y
-
1
:
x
,
y
∈
D
}
has every element that is not in
H
occur the same number of times (such a
D
is called a
...relative difference set
); (ii)
G
=
D
∪
D
(
-
1
)
∪
H
; (iii)
D
∩
D
(
-
1
)
=
∅
. We show that
|
H
|
=
2
, that
H
is central and that
G
is a group with a single involution. We also show that
G
cannot be abelian. We give infinitely many examples of such groups, including certain dicyclic groups, by using results of Schmidt and Ito.
Full text
Available for:
DOBA, EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, IZUM, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UILJ, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
This paper concentrates on a class of pseudorandom sequences generated by combining q-ary m-sequences and quadratic characters over a finite field of odd order, called binary generalized NTU ...sequences. It is shown that the relationship among the sub-sequences of binary generalized NTU sequences can be formulated as combinatorial structures called Hadamard designs. As a consequence, the combinatorial structures generalize the group structure discovered by Kodera et al. (IEICE Trans. Fundamentals, vol.E102-A, no.12, pp.1659-1667, 2019) and lead to a finite-geometric explanation for the investigated group structure.