\def\Tilde{\char126\relax}
\magnification=\magstep{1.1}
\documentstyle{amsppt}
\pagewidth{5.6in}
\TagsOnRight
\input amstex
\topmatter
\title ON INJECTIVITY OF COMBINATORIAL RADON TRANSFORM OF ORDER FIVE  \endtitle
\author Tewodros Amdeberhan and Melkamu Zeleke \endauthor
\address Temple University, Department of Mathematics, Philadelphia, PA 19122 \endaddress
\email [tewodros,melkamu]{\@}math.temple.edu, \newline
{\rom \it \phantom{.....}World Wide Web}: http://www.math.temple.edu/\~{}[tewodros,melkamu]\endemail

\thanks
 We would like to express our deepest gratitude to our advisor Professor Doron Zeilberger for his inspirations and strong support. \endthanks

\abstract In the present work, we give a proof of the injectivity of the combinatorial radon transform of order five.\endabstract
\endtopmatter

\document
The problem of determining members of a set by their sums of a fixed order was posed by Leo Moser and partially settled by Ewell, Fraenkel, Gordon, Selfridge, and Straus. Following the notation of [BL], the general problem can be stated in the following way.\newline\newline
For any given $(k,n) \in \Bbb Z \times \Bbb Z$, with $2\le k\le n$, we choose arbitrarily an n-set $X_n=\{x_1,x_2,...,x_n\}$ then form the set $W_n^k(X_n)=\{\sigma_i\}$ of all sums of k distinct elements of $X_n$ and ask:\newline 
{\it Does there exist an n-set $X_n^\prime$ different from $X_n$ giving rise to the same set of sums as does $X_n$\/}? More formally, we can describe the problem as follows:\newline Define a mapping $W_n^k$ from the set $\{X_n\}$ of all n-sets to the set of all $\binom nk$-sets by the rule:
$$W_n^k(\{x_1,x_2,\dots,x_n\}) = \{x_{i_1}+x_{i_2}+\dots+x_{i_k}: 1\le i_1< i_2< \dots < i_k\le n\}$$ and try to determine whether $W_n^k$ is one-to-one.
\newline\newline {\bf \underbar{Definition}:\/} $W_n^k$ is called a combinatorial radon transform of order k.\newline\newline 
It is known {\bf [E], [FGS], [SS]\/} that $W^k_n$ is injective if 
$$A(n,k,s)=\sum_{i=0}^{k-1} (-1)^i\binom ni(k-i)^{s-1}\ne 0\tag1$$
for each $s$ in $\{1,2,\dots,n\}$. \newline\newline
{\bf\underbar{Remarks}:\/} The following results are also known. 
\roster
\item if $k=2,$ $W^2_n$ is injective for all n which are {\it not\/} a power of 2.
$W^2_n$ is {\it not\/} injective if n is a power of 2 {\bf [SS]\/}.
\item if $k=3,$ $W^3_n$ is injective for all $n\ge3$ and $n\ne3,6,27,$ and $486$. $W_n^k$ is not injective if $n=3, 6, 27,$ {\bf [BL], [EZ]\/} or $486$ {\bf [BL]\/}. 
\item If $k=4,$  $W_n^4$ is injective for all $n\ge4$ and $n\ne 4$ and 8. $W_n^k$ is not injective if $n=4,$ or 8 {\bf [E], [EZ]\/}. Here we would like to point out that while $A(12,4,6)=0$, John Ewell proved $W_{12}^4$ is injective, thereby showing that condition $(1)$, though necessary, is {\it not\/} sufficient.   
\endroster
In this paper, we settle the problem for the combinatorial radon transform of order five.\newline\newline
In the case $k=5$, condition $(1)$ reduces to a polynomial in $n, 2^s, 3^s, 5^s$, and it can be written as:
$W_n^5$ is injective if 
$$\align A(n,5,s)&=n^4-(2^{s+1}+6)n^3+(4\cdot3^s+3\cdot2^{s+1}+11)n^2\\
&-(4\cdot3^s+3\cdot2^{2s+1}+2^{s+2}+6)n+24\cdot5^{s-1}\ne 0\tag2 \endalign$$
for every $s \in \{1,2,\dots,n\}$.\newline\newline
Consider the function 
$$B(n,s)=n^4+a_3 n^3+a_2 n^2+a_1 n+a_0;$$
where\newline 
\phantom{......}$a_3=-2(2^s+3)$\phantom{.................................}
$a_2=4\cdot3^s+3\cdot2^{s+1}+11$\newline 
\phantom{......}$a_1=-2(2\cdot3^s+3\cdot4^s+2^{s+1}+3)$\phantom{......}  $a_0=2^3\cdot3\cdot5^{s-1}$ \newline for integers $1\le s\le n$.\newline\newline
Let $n$ be an integral solution of $$B(n,s)=0.\tag3$$
{\bf \underbar{Note}\/}: $n$ must have the form $$n=2^\alpha\cdot3^\beta\cdot5^\gamma\tag4$$ for $\alpha=0,1,2,3; \beta=0,1;  \gamma=0,1,2,3,\dots,s-1.$\newline\newline
So, throughout this investigation we assume that n has the form $(4)$.\newline Dividing $(3)$ by $n$ we get:
$$\tilde B(n,s) = n^3+a_3 n^2+a_2 n+a_1+ \tilde a_0 = 0\tag5$$ where 
$\tilde a_0=2^{3-\alpha}\cdot3^{1-\beta}\cdot5^{s-1-\gamma}.$
\newline\newline {\bf \underbar{Observations}:\/}
 \roster
\item 
$\alpha$ cannot be 3: if $\alpha=3$, then $\tilde B(n,s) \not\equiv 0$ (mod~2) since $2 \nmid \tilde a_0$, but 2 divides the rest of the terms.
\item $\alpha$ cannot be 2: if $\alpha=2, \beta=1$ then similarly $\tilde B(n,s)\not\equiv 0$ (mod~8) (in fact $\tilde B(n,s)\equiv 4$ (mod~8)).\newline If $\alpha=2,\beta=0$, then likewise $\tilde B(n,s)\not\equiv 0$ (mod~16).
\item $\alpha=1, \beta=1$ is not possible: $\tilde B(n,s)\not\equiv 0$ (mod~8).
\endroster\newline\newline\newline
Hence we gather that n takes one of the forms:
$$n=2\cdot5^{\gamma}~or~n=3\cdot5^{\gamma}~or~n=5^{\gamma}.\tag6$$
\newline\newline 
On the other hand, if $n>2(2^s+3)$, then 
$$n^4+a_3 n^3=n^3(n-2(2^s+3))>0,$$ 
and moreover
$$\align 
a_2 n^2+a_1 n&=n\left\{(4\cdot 3^s+6\cdot 2^s+11)n-(4\cdot 3^s+6\cdot 4^s+2^{s+2}+6)\right\}\\
&>n\left\{(4\cdot 3^s+6\cdot   2^s+11)2^{s+1}-(4\cdot3^s+6\cdot4^s+2^{s+2}+6)\right\}\\
&>n\{(4\cdot 3^s\cdot 2^{s+1}+6\cdot 4^s\cdot 2+5\cdot 2^{s+1}+6\cdot 2^{s+1})\\
& \hphantom{...}-(4\cdot 3^s+6\cdot 4^s+2\cdot 2^{s+2}+6)\}\\
&>0.
\endalign$$
Hence, $B(n,s)>0$ if $n>2(2^s+3)$.
\newline Note however that if $\gamma \ge\frac12 s+1$, then $n>2(2^s+3)$. This implies for such $\gamma$, the equation $B(n,s)=0$ has no integral solution n.
Therefore, in the sequel it suffices to assume that $\gamma<\frac12 s+1$.
\newline\newline
{\bf \underbar{Notation}:\/} Let $ord_px$ denote the exponent of a prime p in the prime factorization of x.\newline\newline
\proclaim{Lemma:} If $5^m\le s<5^{m+1}$ for any fixed $m\ge 0$, then $\mu:=ord_5 \tilde a_1(s)\le m+2$.
\endproclaim
\demo{Proof} Using the {\it binomial theorem\/}\newline
$$(5-x)^s=(-1)^sx^s+(-1)^{s-1}5\cdot s\cdot x^{s-1}+\dots \tag7$$\newline
Let $\tilde a_1:=2\cdot 3^s + 3\cdot 4^s + 2\cdot 2^s + 3$. Then $\tilde a_1=3(4^s+1) + 2(3^s+2^s),$
and in light of (7)  we can rewrite $\tilde a_1$ as 
$$\tilde a_1=(3\cdot 5\cdot s + 2\cdot 5\cdot s\cdot 2^{s-1})+ ...\phantom{..},$$
for s odd.\newline
Writing s in the form 
$$s=k_m5^m+k_{m-1}5^{m-1}+\dots+k_15+k_0; ~0\le k_i\le 4, ~for~ all~i,$$
define $j:=min\{i|k_i\ne 0\}$.
Then $s=k_m 5^s+\dots+k_j 5^j$. Note that $k_m\ge 1, k_j\ge 1$.\newline\newline\newline\newline\newline\newline
Therefore, for s odd,
$$\align
\tilde a_1&=5(3\cdot k_m\cdot 5^m+2\cdot k_m\cdot 5^m\cdot2^{s-1})+...+5(3\cdot k_j\cdot 5^j+2\cdot k_j\cdot 5^j\cdot2^{s-1})+\dots\\
&=5^{m+1}(3+2^s)k_m+\dots+5^{j+1}(3+2^s)k_j+\dots\endalign$$
Hence
$$ord_5\tilde a_1(s)\le j+2\le m+2.$$
For s even,
$$ x^s+(5-x)^s=2 x^s-5 s x^{s-1}+5^2 \binom s1 x^{s-2}- +\dots$$
Thus,
$$\tilde a_1=2(3+2^{s+1})-5 s(3+2^s)+5^2 \binom s1(3+2^s)- +\dots$$
Writing s in the form:
$$s=k_m 5^s+...+k_j 5^j, ~j~as~in~above,$$
we see that 
$$\tilde a_1=2(3+2^{s+1})-k_m 5^{m+1}(3+2^s)- \dots -k_j5^{j+1}(3+2^s)+\dots$$
But $5\nmid(3+2^s)$, while $5\mid(3+2^{s+1})$ as s is even.
Thus $\tilde a_1=2^{s+1}-(3+2^s)\cdot 5(s-2)+\dots~$
is at most divisible by $5^{m+2}$ since $5^m\le s<5^{m+1}$.
Hence if s is even and $5^m\le s<5^{m+1}$, then $Ord_5 \tilde a_1(s)\le m+2.\blacksquare$
\newline\newline\enddemo
Now,
\roster
\item Suppose that $\gamma\ge m+1$. Then $m+1\le\gamma<\frac 12(s+1).$\newline
\phantom{.....}(i) if $s-1-\gamma\ge m+1$, then $\tilde B(n,s)\not\equiv 0 (mod\phantom{.}5^{m+1})$ since  $5^{m+1}\nmid a_1$ by the lemma $\phantom{..........}$above.\newline
\phantom{....}(ii) if $s-1-\gamma<\mu$, then $B(n,s)\not\equiv 0 (mod \phantom{.}5^\mu)$  as $5^\mu \nmid \tilde a_0$.\newline
\phantom{...}(iii) if $s-1-\gamma=\mu$, then $\gamma=s-1-\mu\ge s-1-m$ by the lemma above. But $\phantom{..........}$then $s-1-m<\frac 12s+1$.\newline\newline
Therefore, 
$$5^{m-2}\le s< 2m+4.$$ Hence $m\le 3.$
\item Suppose that $m-2\le \gamma \le m$.\newline
If $m\ge 4$, then $a_0(s)=24\cdot 5^{s-1}>-a_1 n-a_3 n^3$ for n in one of the above forms. We then conclude that $B(n,s)>0$, that is, equation $(3)$ has no integral solution unless $m\le 3$.\newline\newline\newline
\endroster\newline\newline\newline
{\bf \underbar{Conclusion}:\/} In all cases, $m\le 3.$ This shows that it remains to verify whether n in the form (4) is a solution of equation (3) for $0\le \gamma<\frac 12s+1\le\frac 125^2+1\le 14.$ (Recall that for $m\le 3$, we also have $1\le s\le 24.$) That is, we simply test if $$B(n,s)=0~ for~ 0\le \gamma \le 14,~ 1\le s\le 24.\tag8$$
We carried out this test using {\bf Maple\/}\footnote "*"{A short Maple program that carries out the test is available in the {\bf WWW\/} under \newline {\bf http://www.math.temple.edu\Tilde [melkamu,tewodros]\/}.}, and found that (8) is true only if $n=2, 3, 4, 5,~ or~ 10.$\newline\newline
Thus we have proved the following theorem:
\proclaim{Theorem} Let $n$ and $s$
 be positive integers such that $s\le n$. Then $$B(n,s)=0$$ 
only if $n=2, 3, 4, 5,~ or~ 10$.\endproclaim
\proclaim{Corollary} The combinatorial radon transform of order five is injective for all $n\ge 5$ and $n\ne 5,~ and~ 10$.\newline\endproclaim 
{\bf\underbar{Note}:\/} $W_5^5$ is clearly noninjective and $W_{10}^5$ is not injective since 
$$X:=\{0^1,5^6,10^3\} \ne Y:=\{2^3,7^6,12^1\}$$
but 
$$W^5_{10}(X)=W^5_{10}(Y)$$ {\bf [EZ]\/}.\newline\newline\newline\newline
\newline\newline\newline\newline\newline\newline\newline
\newline\newline\newline\newline\newline\newline\newline\newline
{\bf References:\/}\newline\linebreak
{\bf[BL]\/} Jan Boman and Svante Linusson, {\it Examples of non--uniqueness for the combinatorial radon transform mudulo the symmetric group,\/} Mat. Scan., to appear.\newline\linebreak
{\bf[E]\/} John A. Ewell, {\it On the determintion of sets by sets of sums of fixed order,\/} Canadian Journal of Mathematics $20$ (1968), 596--611.\newline\linebreak
{\bf[EZ]\/} Shalosh B. Ekhad and Melkamu Zeleke, {\it Finding examples of noninjectivity for combinatorial radon transform,\/} Preprint.\newline\linebreak
{\bf[G]\/} Richard K. Guy, {\it Unsolved Problems in Number Theory,\/} volume 1. Springer-Verlag, 1981; second edition, 1994.\newline\linebreak
{\bf[FGS]\/} A. S. Fraenkel, B. Gordon and E.G. Straus, {\it On the determination of sums of a certain order,\/} Pacific Journal of Mathematics 12 (1962), 187--196.\newline\linebreak
{\bf[SS]\/} J. L. Selfridge and E. G. Straus, {\it On the determination of numbers by their sums of a fixed order,\/} Pacific Journal of Mathematics 8 (1958), 847--856.\newline\linebreak
 
\enddocument