The Subset Sum game

In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in the knapsack. The solution is built as follows: Each agent, in turn, selects one of its items (not previously selected) and includes it in the knapsack if there is enough capacity. The process ends when the remaining capacity is too small for including any item left.     

Sum of Divisors in a Ring of Gaussian Integers

We construct an asymptotic formula for a sum function for _a (), where _a () is the sum of the ath powers of the norms of divisors of the Gaussian integer on an arithmetic progression ₀ (mod ) and in a narrow sector ₁ arg < ₂. For this purpose, we use a representation of _a (n) in the form of a series in the Ramanujan sums.     

整数集的加权表示的渐进基

Let k1, k2 be nonzero integers with(k1, k2) = 1 and k1k2≠-1. Let Rk1,k2(A, n)be the number of solutions of n = k1a1 + k2a2, where a1, a2 ∈ A. Recently, Xiong proved that there is a set A  Z such that Rk1,k2(A, n) = 1 for all n ∈ Z. Let f : Z-→ N0∪ {∞} be a function such that f-1(0) is finite. In this paper, we generalize Xiong's result and prove that there exist uncountably many sets A  Z such that Rk1,k2(A, n) = f(n) for all n ∈ Z.     

整数集的唯一加权表示基

Let k1, k2 be nonzero integers with(k1, k2) = 1 and k1k2≠-1. In this paper, we prove that there is a set A■Z such that every integer can be represented uniquely in the form n = k1a1 + k2a2, a1, a2 ∈ A.     

Structural Approach to Subset Sum Problems

We discuss results obtained jointly with Van Vu on the length of arithmetic progressions in \(\ell \)-fold sumsets of the form

$$\begin{aligned} \ell \mathcal {A}=\{a_1+\dots +a_\ell ~|~a_i\in \mathcal {A}\} \end{aligned}$$

and

$$\begin{aligned} \ell \mathcal {A}=\{a_1+\dots +a_\ell ~|~a_i\in \mathcal {A}\text { all distinct}\}, \end{aligned}$$

where \(\mathcal {A}\) is a set of integers. Applications are also discussed.

     

一个与Dedekind和相关的新和式及其在特殊点的值

本文利用正整数模q的正则数的定义以及解析方法研究一类与Dedekind和有关的和式的计算问题,并给出这个和式在一些特殊点上有趣的恒等式.     

Representations of Positive Integers by a Direct Sum of Quadratic forms

The number of representation of positive integers by quadratic forms $ F_{1}=x_{1}^{2}+3x_{1}x_{2}+8x_{2}^{2} $ and $ G_{1}=2x_{1}^{2}+3x_{1}x_{2}+4x_{2}^{2} $ of discriminant —23 are given. Moreover, a basis for the cusp form space S ₄(Γ₀(23), 1) are constructed. Furthermore, formulas for the representation of positive integers by direct sum of copies of F ₁ and G ₁, i.e. formulas for $ r(n; F_{4}), r(n; G_{4}), r(n; F_{3} \oplus G_{1}), r(n; F_{2} \oplus G_{2}), {\rm and}\ r(n; F_{1} \oplus G_{3}) $ , are derived using the elements of the space S ₄(Γ(23), 1).     

Representation of Integers by Ternary Quadric Forms

In this paper we give a formula for the number of representations of some square-free integers by certain ternary quadratic forms and estimate the lower bound of the 2-power appearing in this number. Supported by NSFC and RFDP.     

Representation of Integers in Subsequences of the Positive Integers by Binary Quadratic Forms

We consider positive-definite primitive binary quadratic forms of fundamental discriminant d < 0; R is the genus and C is the class of such forms. We obtain asymptotics for the sum of absolute values of the Fourier coefficients for the Hecke eigenforms of weight 1 and of dihedral type. In an earlier paper (Zap. Nauchn. Semin. POMI, 226 (1996)), the author showed that if C R, then almost all R-representable positive integers are C-representable. We extend this result to certain subsequences of such as {a _n = p _n + l}, {a _n = n(n + 1)}, etc. Finally, for certain genera R with class number greater than one, we prove an asymptotics (x ) for the sum

Representation of Integers by Positive Quaternary Quadratic Forms

Let $f(x,y,x,w) = x^2 + y^2 + z^2 + Dw^2$ , where $D >1$ is an integer such that $D \ne d^2$ and ${{\sqrt n } \mathord{\left/ {\vphantom {{\sqrt n } {\sqrt D = n^\theta , 0 < \theta < {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2}}}} \right. \kern-0em} {\sqrt D = n^\theta , 0 < \theta < {1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2}}}$ . Let $rf(n)$ be the number of representations of n by f. It is proved that $r_f (n) = \pi ^2 \frac{n}{{\sqrt D }}\sigma _f (n) + O\left( {\frac{{n^{1 + \varepsilon - c(\theta )} }}{{\sqrt D }}} \right),$ where $\sigma _f (n)$ is the singular series, $c(\theta ) >0$ , and ε is an arbitrarily small positive constant. Bibliography: 14 titles.     

An Identity of Ramanujan and the Representation of Integers as Sums of Triangular Numbers

Let k be a positive number and t _k(n) denote the number of representations of n as a sum of k triangular numbers. In this paper, we will calculate t _2k (n) in the spirit of Ramanujan. We first use the complex theory of elliptic functions to prove a theta function identity. Then from this identity we derive two Lambert series identities, one of them is a well-known identity of Ramanujan. Using a variant form of Ramanujan's identity, we study two classes of Lambert series and derive some theta function identities related to these Lambert series . We calculate t ₁₂(n), t ₁₆(n), t ₂₀(n), t ₂₄(n), and t ₂₈(n) using these Lambert series identities. We also re-derive a recent result of H. H. Chan and K. S. Chua [6] about t ₃₂(n). In addition, we derive some identities involving the Ramanujan function (n), the divisor function ₁₁(n), and t ₂₄(n). Our methods do not depend upon the theory of modular forms and are somewhat more transparent.     

华蘅芳数在幂和问题中的新应用

自然效的幂和问题具有悠久的历史,亦不乏现代的兴趣.一般学者不了解清代数学家华蘅芳的成果.本文改进了华氏数的定义;针对该问题建立了新的取盒-放球模型,给出幂和的组合解释;应用华氏数获得了简捷的幂和公式.文末介绍了华氏数的历史来源.     

On the Distribution in Residue Classes of Integers with a Fixed Sum of Digits

We give an asymptotic formula for the distribution of those integers n in a residue class, such that n has a fixed sum of base-g digits, with some uniformity over the choice of the modulus and g. We then use this formula to solve the problem of I. Niven of giving an asymptotic formula for the distribution of those integers n divisible by the sum of their base-g digits. Our results also allow us to give a stronger form of a result of M. Olivier dealing with the distribution of integers with a given gcd with their sum of base-g digits.For our friend Jean-Louis Nicolas on his sixtieth birthdayResearch partially supported by the Hungarian National Foundation for Scientific Research, Grant No. T029759, and “Balaton” French-Hungarian exchange program F-18/00.2000 Mathematics Subject Classification: Primary—11A63     

Approximability of the Problem of Finding a Vector Subset with the Longest Sum

We answer the question of existence of polynomial-time constant-factor approximation algorithms for the space of nonfixed dimension. We prove that, in Euclidean space the problem is solvable in polynomial time with accuracy \(\sqrt a \), where α = 2/π, and if P ≠ NP then there are no polynomial algorithms with better accuracy. It is shown that, in the case of the ?_p spaces, the problem is APX-complete if p ∈ [1, 2] and not approximable with constant accuracy if P ≠ NP and p ∈ (2,∞).     

Density of Integers That Are the Sum of Four Cubes of Primes

gi. IntroductionIt is conjectured that all sufficielltly large integers e satisfying some necessaly congruenceconditions are the sum of four cubes of primes, i.e.(see e.g. [1]). Such a strong conjecture is out of reach at present; but it is reasonable, inview of the following results of Hua and Davenport respectively. A theorem of Hua[3'4] statesthst almost all positive integers, with t * 0, 12(mod 9) are the sum of five cubes of praies,while DavenPOrt's result in 12] asserts that almost all…     

On the Representation of Integers by the Lorentzian Quadratic Form

In this paper, we establish an asymptotic formula, for large radiusr, for the number of representations of a nonzero integerkby the Lorentzian quadratic formx²₁+x²₂+…+x²_n−x²_n+1that are contained in the ball of radiusrcentered at the origin in Euclidean (n+1)-space.     

A 3/4-Approximation Algorithm for Multiple Subset Sum

The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The problem is also a special case of the multiple knapsack problem in which all knapsacks have the same capacity and the item profits and weights coincide. Recently, polynomial time approximation schemes have been proposed for MSSP and its generalizations, see A. Caprara, H. Kellerer, and U. Pferschy (SIAM J. on Optimization, Vol. 11, pp. 308–319, 2000; Information Processing Letters, Vol. 73, pp. 111–118, 2000), C. Chekuri and S. Khanna (Proceedings of SODA 00, 2000, pp. 213–222), and H. Kellerer (Proceedings of APPROX, 1999, pp. 51–62). However, these schemes are only of theoretical interest, since they require either the solution of huge integer linear programs, or the enumeration of a huge number of possible solutions, for any reasonable value of required accuracy. In this paper, we present a polynomial-time 3/4-approximation algorithm which runs fast also in practice. Its running time is linear in the number of items and quadratic in the number of bins. The core of the algorithm is a procedure to pack triples of large items into the bins. As a byproduct of our analysis, we get the approximation guarantee for a natural greedy heuristic for the 3-Partitioning Problem.     

侧完备Riesz空间中理想的直和及其表示定理

设{Ei：i∈I)是侧完备Riesz空间E中的一族理想，且Ei∩Ej=θ(i，j∈I，i≠j)．文章引入理想族{Ei：i∈I)直和的概念，并给出一个表示定理．文章证明了：存在一个完备的正则Hausdorff空间X使得理想族的直和Riesz同构于C(X)其充要条件是对每个i∈I存在一个紧Hausdorff空间Xi使得Ei Riesz同构于C(X)．     

自然数幂方和用二项系数表示的系数公式

得到了自然数幂方和由二项系数表示的系数a_i~(k)的公式,和由排列数表示的系数b_i~(k)的公式,证明了系数存在唯一性及系数间的若干重要性质,给出了计算系数的C-语言程序.