Search

The subset sum problem is an important theoretical problem with many applications, such as in coding theory, cryptography, graph theory and other fields. One of the many aspects of this problem is to answer the solvability of the k -subset sum problem. It has been proven to be NP-hard in general. However, if the evaluation set has some special algebraic structure, it is possible to obtain some good conclusions. Zhu, Wan and Keti proposed partial results of this problem over two special kinds of evaluation sets. We generalize their conclusions in this paper, and propose asymptotical results of the solvability of the k -subset sum problem by using estimates of additive character sums over the evaluation set, together with the Brun sieve and the new sieve proposed by Li and Wan. We also apply the former two examples as application of our results. [ABSTRACT FROM AUTHOR]

In this paper, we derive an explicit combinatorial formula for the number of k -subset sums of quadratic residues over finite fields. [ABSTRACT FROM AUTHOR]

Let F q be a finite field with q = p e elements, where p is a prime and e ≥ 1 is an integer. Let ℓ , n be two positive integers such that ℓ < n . Fix a monic polynomial u ( x ) = x n + u n − 1 x n − 1 + ⋯ + u ℓ + 1 x ℓ + 1 ∈ F q [ x ] of degree n and consider all degree n monic polynomials of the form f ( x ) = u ( x ) + v ℓ ( x ) , v ℓ ( x ) = a ℓ x ℓ + a ℓ − 1 x ℓ − 1 + ⋯ + a 1 x + a 0 ∈ F q [ x ] . For any non-negative integer k ≤ min { n , q } , let N k ( u ( x ) , ℓ ) denote the total number of v ℓ ( x ) such that u ( x ) + v ℓ ( x ) has exactly k distinct roots in F q , i.e. N k ( u ( x ) , ℓ ) = | { f ( x ) = u ( x ) + v l ( x ) | f ( x ) has exactly k distinct zeros in F q } | . In this paper, we obtain explicit combinatorial formulae for N k ( u ( x ) , ℓ ) when n − ℓ is small, namely when n − ℓ = 1 , 2 , 3 . As an application, we define two kinds of Wenger graphs called jumped Wenger graphs and obtain their explicit spectrum. [ABSTRACT FROM AUTHOR]