|
|
 | | From: | matt | | Subject: | Re: Finding unique sums. | | Date: | 25 Nov 2004 04:37:48 -0800 |
|
|
 | Gerry Myerson wrote in message news:...
> C8 asks about the maximum number of positive integers not exceeding
> 2^k with all subset sums distinct. Conway & Guy conjecture it's
> k + 2 - notice that this is better than the k + 1 you get by taking
> powers of 2. An example that achieves k + 2 is given.
>
I too was convinced that you couldn't do better than powers of 2, and
I'd be very interested to see that example. For those of us who don't
have the book, is the example simple enough for you to reproduce here?
(I'm not asking you to type in ten pages of text!)
|
|
| | From: | Gerry Myerson | | Subject: | Re: Finding unique sums. | | Date: | Fri, 26 Nov 2004 10:03:01 +1100 |
|
|
| In article ,
matt271829-news@yahoo.co.uk (matt) wrote:
> Gerry Myerson wrote in message
> news:...
> > C8 asks about the maximum number of positive integers not exceeding
> > 2^k with all subset sums distinct. Conway & Guy conjecture it's
> > k + 2 - notice that this is better than the k + 1 you get by taking
> > powers of 2. An example that achieves k + 2 is given.
> >
>
> I too was convinced that you couldn't do better than powers of 2, and
> I'd be very interested to see that example. For those of us who don't
> have the book, is the example simple enough for you to reproduce here?
> (I'm not asking you to type in ten pages of text!)
Here are some reviews from Math Reviews, you can probably extract
the information you want (and more!) from them, especially if TeX
doesn't bother you.
MR0917837 (89a:11019)
Lunnon, W. F.(4-WALC)
Integer sets with distinct subset-sums.
Math. Comp. 50 (1988), no. 181, 297--320.
11B13 (94A60)
The set of integers $p_i=2^{i-1}$, $i=1,2,\cdots,n$, has the
interesting property that all of its distinct subsets have distinct
sums. Let us call this property SSD. The question is whether there are
sets $\overline{p}=\{p_0=0$p_n<2^{n-1}$ that have the SSD property. Denote by $[\alpha]$ the
greatest integer not exceeding $\alpha$. Take the sequence
$\overline{v}=\{v_0=0$v_{n+1}=2v_n-v_{n-m}$ for $n\ge1$, where $m=[\tfrac12 n+1]$ (this
sequence is called by the author the "Atkinson-Negro-Santoro sequence").
In the paper it is proved that the sequence $\overline{p}=\{p_i\}$,
where $p_i=v_n-v_{n-i}$, $i=1,2,\cdots,n$, has the SSD property for all
$n$. Another sequence (the "Conway-Guy sequence") $\overline{u}=
\{u_0=0$m=[\tfrac12+\sqrt{2n}]$. It is conjectured that the set
$\overline{p}=\{p_i\}$, $p_i=u_n-u_{n-i}$, $i=1,2,\cdots,n$, is also SSD
for all $n$. The author investigates this conjecture. The sequence
$\overline{w}=\{w_0=0distinct subsets of the same cardinality have distinct sums (a weakening
of SSD). The author proves that, for some fixed $n$, if $\overline{u}$
is SSDO, then $p_i=u_n-u_{n-i}$ is SSD. It is not known whether
$\overline{u}$ is SSDO for all $n$. It is proved in the paper that the
set $\{u_0,u_1,\cdots,u_{n-1},x\}$ is not SSDO if $xthis property, the author introduces the generalized Conway-Guy sequence
as follows: Given $w_0smallest natural number which cannot be written in the form $\sum_{i\in
I} w_i-\sum_{j\in J}w_j$, where $I,J\subset(1,\cdots,n-1)$, $I\cap J
=\varnothing$ and $|I|-|J|=1$ $(|·|$ means the cardinality of the set).
Setting $w_0=0$, this sequence is SSDO and is for $n<80$ identical to
$\overline{u}$. The author defines other such sequences $\overline{w}$
where $w_0\ne0$ and investigates whether these are SSDO for all $n$.
The paper contains many other results about the above question; among
other things some algorithms are proposed to verify the SSD property.
One of the algorithms gives that $\overline{u}$ is SSDO, and hence
$\overline{p}$ defined by it is SSD if $n<80$. In the paper two
interesting tables of concrete values can be found and
$\lim_{n\rightarrow\infty}z_n/2^{n-1}$ is also computed for
$\overline{z}=\overline{v}$, $\overline{u}$ or $\overline{w}$.
Reviewed by Béla Uhrin
MR1954968 (2003k:11036)
Borwein, Peter(3-SFR-MS); Mossinghoff, Michael J.(1-UCLA)
Newman polynomials with prescribed vanishing and integer sets with
distinct subset sums. (English. English summary)
Math. Comp. 72 (2003), no. 242, 787--800 (electronic).
11C08 (11B75 11Y55)
Let $d(m)$ be the minimal degree of a polynomial that has all
coefficients in $\{0,1\}$ and a zero of multiplicity $m$ at $-1$. A
greedy solution can be defined as follows. Let $J_1=1$ and $J_k$ be the
least odd integer greater than $J_1+\dots+J_{k-1} (k>1)$. It is easy to
see that the polynomial $g_m(x)=\prod_{k=1}^m(1+z^{J_k})$ has the
above-defined properties and that $$\deg
g_m=\frac43·2^m-\frac32+\frac{(-1)^m}6.$$ Therefore,
$$d(m)\le\frac43·2^m-\frac32+\frac{(-1)^m}6.$$ The authors show that the
equality holds if and only if $m\le5$. In the general case, they prove
that $$2^m+c_1m\le d(m)\le \frac{103}{96}·2^m+c_2$$ and they conjecture
that for any $\epsilon>0$ the inequality $d(m)<(1+\epsilon)2^m$ holds
for sufficiently large $m$. Also, they consider the related problem of
finding a set of $m$ positive integers with distinct subset sums and
minimal largest element and show that the well-known Conway--Guy
sequence yields the optimal solution for $m\le9$.
Reviewed by Serge\u\i V. Konyagin
MR1486396 (98k:11014)
Bohman, Tom(1-MIT)
A construction for sets of integers with distinct subset sums.
(English. English summary)
Electron. J. Combin. 5 (1998), Research Paper 3, 14 pp. (electronic).
11B75 (05D10)
A finite set $S$ of positive integers has distinct subset sums if the
$2\sp{|S|}$ sums $\sum\sb{a\in A}a$, where $A\subseteq S$, are pairwise
distinct. For brevity, call sets with distinct subset sums DSS-sets. The
paper investigates the following questions: How small can a positive
integer $N$ be such that $\{1,2,\cdots,N\}$ contains an $n$-element
DSS-set?
For every $n$ let $f(n)$ be the smallest $N$ with this property. In
different terms: $f(n) = \min \max_S N$, where the minimum is taken over
all $n$-element DSS-sets. Obviously, $f(n)\le 2\sp {n-1}$ (take
$S=\{1,2,4,\cdots,2\sp{n-1}\})$. Erdös conjectured that $f(n)\gg 2\sp n$
(the implicit constant is absolute). Together with Moser he proved in
1955 a weaker inequality $f(n)\ge 2\sp n /(4\sqrt n)$, which remains, up
to the constant, the best known lower bound for $f(n)$.
In the opposite direction, J. H. Conway and R. K. Guy \ref[Notices
Amer. Math. Soc. 15 (1968), no. 2, 345, Abstract 654-32] constructed
"short" DSS-sets, using a special sequence of integers they discovered
(the Conway-Guy sequence). Their result implied an estimate $f(n) \le
0.23513·2\sp n$ for $n\ge 40$. W. F. Lunnon\ \ref[Math. Comp. 50 (1988),
no. 181, 297--320; MR0917837 (89a:11019)] suggested a similar
construction, which implied $f(n) \le 0.22096 ·2\sp n$ for $n\ge 67$.
In his paper Bohman presents two parametric families of infinite
sequences, which include, for small values of parameters, the sequences
of Conway-Guy and Lunnon. Using his sequences, he finds many new
examples of DSS-sets, and, in particular, obtains a new upper estimate
$f(n) \le 0.22002 ·2\sp n$ for sufficiently large $n$. Bohman's
construction is very subtle and interesting and is likely to find
different applications in combinatorics, cryptography, and related
fields.
Reviewed by Yuri Bilu
MR1464377 (98i:11012)
Maltby, Roy(3-CALG)
Bigger and better subset-sum-distinct sets. (English. English summary)
Mathematika 44 (1997), no. 1, 56--60.
11B75
A set of natural numbers is called subset-sum-distinct (SSD) if all
pairwise distinct subsets have unequal sums. If $A$ is any SSD set,
define $\alpha(A)=(\max A)/2^{|A|-1}$, where $\max A$ is the biggest
element of $A$. Given an SSD set, it is shown how to construct a bigger
SSD set whose $\alpha$-ratio is smaller. This shows that
$\inf\{\alpha(A)\colon A$ is an SSD set\}is not realised by any SSD set.
(Erdös asked if the inf is positive.) The author also points out that
one of the claims of W. F. Lunnon \ref[Math. Comp. 50 (1988), no. 181,
297--320; MR0917837 (89a:11019)] concerning SSD sets is false.
Reviewed by Ian Anderson
MR1363448 (97b:11027)
Bohman, Tom(1-RTG)
A sum packing problem of Erdös and the Conway-Guy sequence. (English.
English summary)
Proc. Amer. Math. Soc. 124 (1996), no. 12, 3627--3636.
11B75
A set $A$ of positive integers has distinct subset sums if the set
$\{\sum_{x\in X}x\colon X\subseteq A\}$ has $2^{|A|}$ distinct elements.
J. H. Conway and R. K. Guy \ref[Notices Amer. Math.\ Soc. 15 (1968),
345] defined a sequence, $\{A_k\}$, of sets of integers as follows: (1)
let $u_0=0, u_1=1$, and, for $n\geq1,\ u_{n+1}=2u_n-u_{n-r}$, where $r$
is the closest integer to $\sqrt{2n}$; (2) for each $k\geq1$, define
$A_k=\{u(k+1)-u(i)\colon1\leq i\leq k\}$. They conjectured that for
every $k, A_k$ has distinct subset sums, and they showed this to be true
for $1\leq k\leq40$. W. F. Lunnon \ref[Math. Comp. 50 (1988), no. 181,
297--320; MR0917837 (89a:11019)] extended this to all $k\leq80$. In
this paper the author establishes the conjecture of Conway and Guy for
all $k$. Define $f(n)=\min\{\max_{s\in S}s\colon|S|=n$ and $S$ has
distinct subset sums\}. The Conway-Guy sequence mentioned above gives
rise to $2^{n-2}$ as an upper bound on $f(n)$. This bound was improved
by Lunnon to $0.2246(2^n)$. In this paper, the author presents a
modification of the Conway-Guy sequence, and states that this leads to a
slight improvement over Lunnon's bound, namely $0.22002(2^n)$. The
author does not include a proof of this statement here, but plans to
include it in a later paper.
Reviewed by Bruce Landman
--
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email)
|
|
| | From: | Denis Leger | | Subject: | Re: Finding unique sums. | | Date: | Thu, 25 Nov 2004 16:30:48 +0100 |
|
|
| matt a écrit :
> Gerry Myerson wrote in message
> news:...
>> C8 asks about the maximum number of positive integers not exceeding
>> 2^k with all subset sums distinct. Conway & Guy conjecture it's
>> k + 2 - notice that this is better than the k + 1 you get by taking
>> powers of 2. An example that achieves k + 2 is given.
>>
>
> I too was convinced that you couldn't do better than powers of 2, and
> I'd be very interested to see that example. For those of us who don't
> have the book, is the example simple enough for you to reproduce here?
> (I'm not asking you to type in ten pages of text!)
C'est un forum en français, respectez la charte !
--
Denis Léger
|
|
| | From: | Ilan Vardi | | Subject: | Re: Finding unique sums. | | Date: | 25 Nov 2004 14:10:05 -0800 |
|
|
| Vous avez aussi poste ce message a des forums anglais, donc vous
n'avez pas respecte leurs chartes.
-ilan
Denis Leger wrote in message news:<8eah72-ubc.ln1@athlon.maison>...
> matt a écrit :
>
> > Gerry Myerson wrote in message
> > news:...
> >> C8 asks about the maximum number of positive integers not exceeding
> >> 2^k with all subset sums distinct. Conway & Guy conjecture it's
> >> k + 2 - notice that this is better than the k + 1 you get by taking
> >> powers of 2. An example that achieves k + 2 is given.
> >>
> >
> > I too was convinced that you couldn't do better than powers of 2, and
> > I'd be very interested to see that example. For those of us who don't
> > have the book, is the example simple enough for you to reproduce here?
> > (I'm not asking you to type in ten pages of text!)
>
> C'est un forum en français, respectez la charte !
|
|
| | From: | matt | | Subject: | Re: Finding unique sums. | | Date: | 25 Nov 2004 15:03:32 -0800 |
|
|
| Denis Leger wrote in message news:<8eah72-ubc.ln1@athlon.maison>...
> matt a écrit :
>
> > Gerry Myerson wrote in message
> > news:...
> >> C8 asks about the maximum number of positive integers not exceeding
> >> 2^k with all subset sums distinct. Conway & Guy conjecture it's
> >> k + 2 - notice that this is better than the k + 1 you get by taking
> >> powers of 2. An example that achieves k + 2 is given.
> >>
> >
> > I too was convinced that you couldn't do better than powers of 2, and
> > I'd be very interested to see that example. For those of us who don't
> > have the book, is the example simple enough for you to reproduce here?
> > (I'm not asking you to type in ten pages of text!)
>
> C'est un forum en français, respectez la charte !
Please accept my apologies. I didn't notice that this was being posted
to a French-language group.
|
|
|
