most recent 30 from http://mathoverflow.net 2013-06-20T11:14:02Z http://mathoverflow.net/feeds/question/98200 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98200/lower-bounding-the-number-of-summands-in-a-sum-representation-of-a-nonnegative-fu sebastian 2012-05-28T16:02:11Z 2012-05-28T16:02:11Z

<p>Hi everybody,</p> <p>let $f: [n] \times [n] \rightarrow \mathbb R_+$ be a nonnegative function and suppose that $f = \sum_{i = 1}^m f_i$ where the $f_i: [n] \times [n] \rightarrow \mathbb R_+$ however each $f_i$ can only use a limit amount of the input (say O(\log n) or even less) bits. Now I want to lower bound the number of needed summands $r$ in such a representation. Clearly, this depends heavily on $f$. Is there an associated theory or a field that deals with this type of questions (or that can answer such questions)? Any pointers or links are much appreciated! Maybe some Fourier-type arguments?</p> <p>I believe that arguments will use some kind of "blindness" of the $f_i$, i.e., one takes elements w.r.t. some of the $f_i$ are constant (indifferent) and then one takes a superposition of the functions which violates linearity. If $f$ itself is "linear", say such as $f(S) = |S|$ then often a small representation can be found; here we write $f(S) = |S| = \sum_{i = 1}^n \chi(i \in S)$ which needs only $n$ summands and each $f_i$ uses only $1$ bit of the input. However I am mostly interested in lower bound on $r$.</p> <p>Thanks a lot, Sebastian </p>