# How does the 'Flatten' function reduce the coefficients of a vector/matrix?

Seen here, at the bottom of page 5, $$\operatorname{Flatten}(\vec{a})$$ is defined as:

$$\operatorname{Flatten}(\vec{a})=\operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1}(\vec{a}))$$

For an n-dimensional vector $$\vec{a} = (a_{1,0},\ldots,a_{1,l}, \ldots, a_{k,0},\ldots,a_{k,l-1})$$. Where $$a_{i,j}$$ is the $$j$$-th bit in $$a_i$$'s bit representation.

But if we're computing the function through its own inverse, would this not just result in the original vector a?

When all the entries of $$a$$ are binaries, then yes, $$Flatten(a) = a$$, because $$BitDecomp^{-1}(a)$$ will give a $$k$$-dimensional vector whose entries are decomposed back to $$\ell$$ consecutive entries of $$a$$ (by $$BitDecomp$$).

However, when $$a$$ has non-binaries entries, this is not the case.

For instance, for $$\ell = 3$$ and $$k = 2$$, we would have $$N = 6$$. Then, consider $$a = (0, 3, 0, 0, 0, 1)$$.

Then, $$BitDecomp^{-1}(a) = (3\cdot 2, 1\cdot 4) = (6, 4)$$, and $$BitDecomp(6, 4) = (0, 1, 1, 0, 0, 1)$$.

Notice that for the last block of $$a$$ (last $$\ell$$ entries), $$Flatten$$ worked as the identity, because this block was binary.

• Thank you for your response. Would this still hold, when the entries are non-binary, if $\sum a_{1,j}> 7$, therefore couldn't be represented in $l$-bits? For example, if $a=(5,3,1,0,0,1)$ and the values of $l,k$ remain, would $Flatten(a)$ still be valid? Apr 3, 2019 at 14:56
• @Stilton yes, it would work modulo $q$. Actually, you perform the operations modulo $q$ and $\ell = \lceil \log q \rceil$, thus, all the produced values can be represented with $\ell$ bits. Feb 7, 2020 at 7:34
• For clarity, you might note that bits ordered least significant to most significant. Feb 7, 2020 at 7:57