An issue has cropped up recently in programming with which I could greatly benefit from the expertise of proper mathematicians. The real-world problem is that apps often need to download huge chunks of data from a server, like videos and images, and users might face the issue of not having great connectivity (say 3G) or they might be on an expensive data plan.

Instead of downloading a whole file though, I've been trying to prove that it's possible to instead just download a kind of 'reflection' of it and then using the powerful computing of the smartphone accurately reconstruct the file locally using probability.

The way it works is like this:

1. A file is broken into its bits (1,0,0,1 etc) and laid out in a predetermined pattern in the shape of a cube. Like going from front-to-back, left-to-right and then down a row, until complete. The pattern doesn't matter, as long as it can be reversed afterwards.
2. To reduce file size, instead of requesting the whole cube of data (the equivalent of downloading the whole file), we only download 3 x 2D sides instead. These sides I'm calling the reflection for want of a better term. They have the contents of the cube mapped onto them.
3. The reflection is then used to reconstruct the 3D cube of data using probability - kind of like asking a computer to do a huge three-dimensional Sudoku. Creating the reflection and reconstructing the data from it are computationally heavy, and as much as computers love doing math, I'd like to lighten their load a bit.

The way I'm picturing is like a 10x10 transparent Rubik's cube. On three of the sides, light is shone through each row. Each cell it travels through has a predetermined value and is either on or off (either binary 1 or 0). If it's on, it magnifies the light by its value. If it is off, it does nothing. All we see is the final amount of light exiting each row, after travelling through the cube from the other side. Using the three sides, the computer needs to determine what values (either 1 or 0) are inside the cube.

At the moment I'm using normal prime numbers as the cell values to reduce computing time, but I'm curious to know if there is another type of prime (or another type of number completely) that might be more effective. I'm looking for a series of values that has the lowest possible combination of components from within that series.

Here is a rough diagram:

It might help to imagine that light shines in at the green arrows, and exits with some value at the red arrows. This happens for each row, in each of the three directions. We're left with only three 2D sides of numbers, which are used to reconstruct what's inside the cube.

If you look where the 14 exits on the left, it can have two possible combinations, (3 + 11 and 2 + 5 + 7). If for arguments sake we were to assume it were 3 and 11 (coloured green), then we could say at the coordinate where 3 and 11 exist, there are active cells (magnifying the light by their value). In terms of data, we would say this is on (binary 1).

In practice we can rarely say for certain (for 2 and 3 we could) what an inside value has based on its reflection on the surface, so a probability for each is assigned to that coordinate or cell. Some numbers will never be reflected on the surface, like 1, 4 or 6, since they can't be composed of only primes.

The same happens in the vertical direction, where the output is 30, which has multiple possibilities of which two correspond to the possibility shown in the horizontal direction with an exit of 14, coloured blue and pink (since they hit the 23, the same as 3 in the horizontal direction).

This probability is also added to that coordinate and we repeat in the front-to-back direction, doing the same a final time. After this is done for each cell in the whole cube, we have a set of three probabilities that a cell is either on or off. That is then used as the starting point to see if we can complete the cube. If it doesn't 'unlock' we try a different combination of probabilities and so forth until we have solved the 3D Sudoku.

The final step of the method is once the cube is solved, the binary information is pulled out of it and arranged in the reverse pattern to how it was laid out on the server. This can then be cut up (say for multiple images) or used to create a video or something. You could cough in theory cough download something like Avatar 3D (280GB) in around 3 minutes on decent wifi. Solving it (nevermind building the pixel output) would take a while though, and this is where I'm curious about using an alternative to prime numbers.

You might have guessed that my maths ability goes off a very steep cliff beyond routine programming stuff. There are three areas of concern / drawbacks to this method:

1. it is rubbish at low levels of data transfer. A 10 x 10 x 10 cube for instance has a larger 'surface area' than volume. That's because while each cell can hold one bit (either 1 or 0), each surface cell needs to be a minimum of 8 bits (one character is one byte, or 8 bits). We can't even have 'nothing', since we need null to behave as a type of placeholder to keep the structure intact. This also accounts for why in the above diagram, a 1000x1000x1000-cell cube has its surface areas multiplied by 4 characters (the thousandth prime is 7919 - 4 characters) and the 10'000(cubed)-cell cube has its surface areas multiplied by 6 characters (10'000th prime is 104729, six characters). The aim is to keep total character length on the 2D side to a minimum. Using letters could work, as we could go from a-Z with 52 symbols, before paying double bubble for the next character (the equivalent to "10"). There are 256 unique ASCII characters, so that's the upper limit there.
2. the factorials are still too high using prime numbers. Is there a series of numbers that are both short in character length (to avoid the problem above) and have very few possible parents? I'm leaning towards some subset of primes, but lack the maths to know which - some sort of inverted Fibonacci? The fewest possible combinations, the faster the computer will solve the cube.
3. I haven't tested yet if its possible to use a third, fourth or nth side to increase either the capacity of the cube or the accuracy of the reflection. Using a say octahedron (yellow below) instead of a cube might be better, just hurts the brain a little to picture how it might work. I'm guessing it would tend towards a sphere, but that's beyond my ability.

EDIT:

Thank you for your helpful input. Many answers have referred to the Pigeonhole principle and the issue of too many possible combinations. I should also correct that a 1000 x cube would require 7 digits not 4 as I stated above, since the sum of the first 1000 primes is 3682913. I should also emphasise the idea isn't to compress in the common sense of the word, as in taking pixels out of an image, but more like sending blueprints on how to build something, and relying only on the computation and knowledge at the receiving end to fill in the blanks. There is more than one correct answer, and will mark correct the one with the most votes. Many thanks for the detailed and patient explanations.

• I know as much about the subject that you are broaching as I do about life on the planet Neptune. Given that, from a black box perspective, it seems that image compression has already been studied with respect to storing graphics as "jpeg" files (e.g. *.jpg). The idea is that typical graphic software allows you to specify the level of compression that will be used to store the *.jpg file. The greater the compression, the more data is lost and the smaller the file size. So, if you could study the jpeg compression algorithm, you might be able to avoid re-inventing the wheel. Sep 13, 2021 at 8:58
• X-ray tomography tries to do this, although it can't choose to replace densities with prime numbers etc. The Radon transform is relevant. But if the original data contains 1000 bits, then the transmitted data needs to say which of the $2^{1000}$ possible images it is, so the transmitted data needs 1000 bits as well. Compression comes because neighbouring pixels in actual images are overwhelmingly similar to each other, so near enough is good enough. Sep 13, 2021 at 9:42
• A basic observation: There are $2^n$ different bit strings of length $n$. If your algorithm compresses every string of length $n$ down to some smaller length $m$, then it has (far) fewer possible output strings to use than the number of possible inputs, so many input files will have the same compressed representation, so the decompression procedure has no way to distinguish them.
– Karl
Sep 13, 2021 at 16:54
• There is a minimum information content to a file. You fundamentally cannot compress it below this content level. File compression works because most files are highly redundant: the actual information content is far smaller than the file size. But just recognize that there is a limit, and there are algorithms out there that get reasonably close to it. you will only be able to beat them by small amounts. With images and sound, you can often go a little further by allowing some loss of information without noticable degradation of the image/sound quality ("lossy algorithms"), depending on the use. Sep 13, 2021 at 17:25
• I haven't voted on this, but if I did, I'd be tempted to downvote because of two things: (1) the question suggests you're completely unaware of some basic principles of information theory (e.g. pigeonhole principle) that would prevent this from working as well as you seem to think it would (2) it also suggests you really think you can beat the performance of other compression algorithms with this approach. To me, that suggest a certain level of arrogance and disdain for existing expertise in this area. I'm sure you didn't intend for it to come across that way, but to me it does. Sep 13, 2021 at 23:20

Universal lossless compression is impossible, this cannot work. The set of binary strings of length $$n$$ is not injective to the set of binary strings of length $$n-1$$.

There are $$2^{n}$$ binary strings of length $$n$$. Let us call the set of all binary strings of given length $$S_{k}$$. When $$k=n-1$$, there are $$|S_{n-1}| = 1+2+2^{2}...+2^{n-1}=2^{n}-1$$

Since $$2^{n} > |S_{n-1}|$$, the pidgeon hole principle implies that there is no injective function from the set of all binary strings of length $$n$$ to any $$S_{k}$$ for $$k. This means that a perfect lossless compression scheme such as the one described is an impossibility since it would constitute such a function.

Furthermore, for any number $$n$$ there exists a string of length $$n$$ whose Kolmogorov-Chaitin complexity is $$n$$.

If you assume this is not the case you have some function $$g:P \to X$$ where $$p_{x} \in P$$ is a program encoding a string $$x \in X$$ whose complexity $$C(x)<|x|$$. such that $$g(p_{x})=x$$ and$$|p_{x}|< |x|$$. We also know that $$x \neq y \implies p_{x} \neq p_{y}$$. Again by the pigeon hole principle if all $$2^{n}$$ strings of length $$n$$ have a program whose length is less than $$n$$, of which there can only be $$2^{n}-1$$, there must be a program that produces two different strings, otherwise the larger set isn't covered. Again this is absurd, so at least one of these strings has a complexity of at least its own length.

Edit: To questions about lossy compression, this scheme seems unlikely to be ideal for the vast majority of cases. You have no way of controlling where and how it induces errors. Compression schemes such as H.264 leverage the inherent visual structure of an image to achieve better fidelity at lower sizes. The proposed method would indiscriminately choose a solution to the system of equations it generates, which would likely introduce noticeable artifacts. I believe that it's also possible for these systems to be overdetermined, using unnecessary space, whereas a DCT is an orthogonal decomposition.The solution of these equations would also probably have to be found using a SAT/SMT solver, whose runtime would also make decompression very costly if not intractable, while DCT based techniques are well studied an optimized for performance, though I am not an expert on any of these subjects by any means.

Full credit for an excellent question on which you have spent a lot of creative energy. This is a comment rather than an answer because it is too long for the usual comment box.

You have an interesting idea and please do continue to investigate it, but did you know data compression has a very wide research base already? You may want to investigate in case your idea, or something similar, is already available. There is a Wikipedia article on compression as an entry point to the subject.

A few observations are:

1. Sound, movie and picture files in use by most applications are all highly compressed, usually (but not always) using imperfect algorithms with an associated loss of data. Formats like zip, jpeg, mp3, mov and even png, are therefore not 'ready to go on arrival' but need sometimes extensive processing before use. Algorithms have developed a lot over the last 50+ years and in some cases are highly sophisticated.

2. In general, compression exploits regularity in the original data (like a photo, where large parts of the image may be similar, or text where the message may only use a small number of different words) and works less well or not at all when file data are truly random.

3. In some applications, data loss can be acceptable, for example in a picture or in music where the eye or ear cannot really see or hear small imperfections, and in these cases very high levels of compression can be obtained (e.g. 90% reduction in size). But for many purposes you need guaranteed perfect results as loss of accuracy simply won't be acceptable, for instance in a computer program file or in text. The data can often still be compressed, exploiting existing regularity, but a saving is not guaranteed in every case.

A final comment on these observations is that applying compression twice is rarely effective because regular data once compressed becomes much less regular and so less susceptible to further compression, so trying to compress a jpg or mp3 file will not usually save anything and may even cost space.

• Thanks for your response. I imagine most optimisation is intelligent, as in for an image of a blue sky say, it might look for that regularity in the form of similar blue pixels, and if from say coordinates (0,0) to (1000,0) it's all blue, cut it. The cube method above is comparatively dumb, or apathetic. If it were used for that blue sky, it's not "taking any pixels out" (lossless), so it could be run on an already optimised image. The heavy lifting is the processing power to "guess" the data. It's not optimising the image in that sense, more capturing a shadow of its data and rebuilding it. Sep 13, 2021 at 13:27
• I would suggest either linking to, quoting, or paraphrasing this section as it is directly relevant to what OP is trying to accomplish. Sep 13, 2021 at 18:51
• I think this is a great answer to this question, but it might be worth pointing out that the most commonly used compression algorithms on the web are well-known not to be optimal and have existing successors, but JPG, PNG, MP3, MP4, etc are commonly supported and well-known so people stick with them. Sep 13, 2021 at 20:15
• It sounds to me like the idea here is you make the cube then have some sort of AI trained to guess the filling. (In other words, the exact cube shape is not so relevant to the core idea as it is having the AI to guess the rest of the data given a part. One could just as well just lop out every other byte, say, and then do the same [that's 50% compression].) Sep 14, 2021 at 0:21
• The extra information, then, is in the AI's neural net. Sep 14, 2021 at 0:25

I'll start off by confessing that I didn't read the entire description of your compression scheme in detail. I don't really need to, since what you're trying to accomplish is an input-agnostic lossless data compression scheme, and that's impossible.

Theorem 1: There is no lossless compression scheme that maps every file of length $$n$$ bits to a file of length less than $$n$$ bits.

The proof follows easily from the pigeonhole principle and the fact that there are $$2^n$$ distinct files of $$n$$ bits but only $$2^n-1$$ distinct files of less than $$n$$ bits. This implies that any compression scheme mapping $$n$$-bit files to files of less that $$n$$ bits must map at least two input files to the same output file, and thus cannot be lossless.

Theorem 2: There is no lossless compression scheme for which the average length of the output files is shorter than the average length of the input files (with averages taken over all possible input files at most $$n$$ bits long, for any non-negative integer $$n$$).

This stronger theorem is slightly trickier to prove. To keep it short, I'll assume you're familiar with basic set-theoretic notation, such as $$R \cup S$$ for the union, $$R \cap S$$ for the intersection and $$R \setminus S = \{x \in R : x \notin S\}$$ for the difference of the sets $$R$$ and $$S$$.

We do need a bit of extra notation. Specifically, let $$\operatorname{len}(x)$$ denote the length of the file $$x$$, and let $$\operatorname{len}(S) = \sum_{x \in S} \operatorname{len}(x)$$ denote the summed total length of all files in the set $$S$$. Thus the average length of files in $$S$$ is $$\frac{\operatorname{len}(S)}{|S|}$$, where $$|S|$$ is the number of files in $$S$$. Also $$\operatorname{len}(R \cup S) = \operatorname{len}(R) + \operatorname{len}(S)$$ for any two disjoint sets of files $$R$$ and $$S$$.

Now let $$f$$ be a lossless compression scheme, i.e. a function mapping files to files, let $$A$$ be the set of all files of length at most $$n$$ bits, and let $$B = \{f(x) : x \in A\}$$ be the set of files obtained by applying $$f$$ to each file in $$A$$. Since $$f$$ is lossless, it must map each input file in $$A$$ to a distinct output file; thus $$|B| = |A|$$, and thus also $$|A \setminus B| = |B \setminus A|$$.

Since $$A$$ is the set of all files at most $$n$$ bits long, it follows that $$\operatorname{len}(x) ≤ n$$ if and only if $$x \in A$$. Thus $$\operatorname{len}(A \setminus B) ≤ n \cdot |A \setminus B| = n \cdot |B \setminus A| ≤ \operatorname{len}(B \setminus A)$$ (where the second inequality is strict unless $$A = B$$, implying that $$A \setminus B = B \setminus A = \emptyset$$).

Furthermore, since $$A \cap B$$ is disjoint from both $$A \setminus B$$ and $$B \setminus A$$, \begin{aligned}\operatorname{len}(A) &= \operatorname{len}(A \cap B) + \operatorname{len}(A \setminus B) \\ &≤ \operatorname{len}(A \cap B) + \operatorname{len}(B \setminus A) \\ &= \operatorname{len}(B).\end{aligned} And since $$|A| = |B|$$, as noted above, we thus have $$\frac{\operatorname{len}(A)}{|A|} ≤ \frac{\operatorname{len}(B)}{|B|}$$ (where, again, the inequality is strict unless $$A = B$$).

Ps. So how do real-world lossless compression schemes work, then? Simply put, they rely on the fact that most "natural" files (containing uncompressed image or sound data, program code, text, etc.) tend to be highly repetitive and quite unlike a random file of similar length. Basically, those "natural" files form only a small subset of all files of their length, and clever compression software can identify such repetitive files and shorten them, while (slightly) increasing the length of other, more random-looking input files.

It's also possible to do this in a way that is guaranteed to never increase the length of any file by more than a small fixed number of bits even in the worst case. In fact, it's possible to take any lossless compression scheme $$f$$ and turn it into a scheme $$f'$$ that is nearly as efficient and only ever increases the length of any input file by at most one bit: simply define $$f'(x) = \begin{cases} (0, f(x)) & \text{if } \operatorname{len}(f(x)) < \operatorname{len}(x) \\ (1, x) & \text{otherwise,} \end{cases}$$ where $$(b, x)$$ denotes prepending the bit $$b$$ to the file $$x$$.

• It is true that you cannot make a lossless compression scheme this way. But the OP mentioned sending videos and images - things that don't necessarily need lossless compression. Could this make the basis of perhaps a good lossy compression method for those, or would it not have any advantages to existing methods (e.g. H.264 and the like)? The idea basically seems to be using some sort of guess as to the "most probable" data, not the exact one that was actually encrypted. So we're talking about lossy compression. Nonetheless, there's still a hard limit when you bite off Sep 14, 2021 at 0:14
• @The_Sympathizer, If I understand OP's question correctly, they are trying to accomplish a file format agnostic lossy compression technique. Most lossy compression techniques rely on removing information that human senses can overlook, this varies with the kind of information, so we have different techniques for different formats. A common technique might not work because you may remove a certain % of information from, lets say, audio and not notice it, but remove the same % of information from video and you might. Sep 14, 2021 at 5:54
• @Johnny The difference is that in a Sudoku, the rows, columns and boxes must obey fixed rules, which let us solve the puzzle. A general image (or other file) isn't constrained like that. However, most useful / interesting data does have various kinds of patterns, and a compressor can encode that pattern info in a more compact way. The tricky part is extracting those patterns because there is no general algorithm that can do that for all possible patterns. Sep 14, 2021 at 7:58
• @JohnnyRockex Yes, but there are many Sudoku problems that can't be solved like you are imagining – they have multiple solutions, so there's no way to know which one is right. This is the pigeon hole principle – if there are more solutions (aka possible files in the world) than representations (your good idea for reflections), then you can't always find the right solution given a representation. Sep 14, 2021 at 11:48
• It may be useful to look at the Mathematics of Sudoku. In particular, it's worth noting that only a tiny fraction of Latin Squares (each value appears in each row and each column) are Sudoku (each value appears in each 3x3 grid). For a 9x9 its 0.0000012 of them that are Sudoku puzzles. And that's when you already assume its a Latin square. The Sudoku actually starts with quite a lot of structure that you know about from the start. It makes the solving process doable. Sep 14, 2021 at 14:47

As others have pointed out, this cannot work for general reasons.

However, you may be more interested in understanding where your analysis for this specific scheme breaks down.

Consider a cube of $$n^3$$ bits. In each row there are $$2^n$$ different combinations, so if you can store $$k$$ values for each entry on one of the three sides, you can at best reduce the number of possibilities to $$2^n/k$$.

In your example for $$n=1000$$ and using primes, you have to and able to store not actually values up to 7919, but you to the sum of the first 1000 primes, which requires 7 decimal digits. In any case, there would be 10000000 different values to encode $$2^{1000}\approx 10^{300}$$ different combinations, so in the best case, one value on the side corresponds to $$10^{293}$$ different combinations of bits in that row. Even projecting in the different directions won't make a significant difference.

If you want to make this work, you need many more digits to store your sums, or go to a very high dimension rather than 3. In both cases the required extra data to transmit will be equal to our exceed the original amount of data.

• Thank you for your answer. To your first point - my mistake - the primes on the side of the cube are like coordinates, and the maximum possible output is the sum of those coordinates - 3682913, which is 7 digits. This would be a row full of binary ones - unlikely but possible. Where there are fewer, we don't need to transfer 7 characters. Even assuming an equal 1/0 ratio though the sum of the first 500 primes is 824693, still 6 digits, not the 4 digits I stated in the question. Sep 14, 2021 at 8:54
• On the second point, those are large numbers :P So going small to start, and ignoring the data cost, taking a Rubik's cube of 3x3x3 and randomly assigning any of the 27 cells as either on or off, each row has 8 possible combinations, right? A regular computer would eat that up - but somewhere along the way to n = 1000, it stops working - not because of any mathematical reason, but because we don't have Deep Thought in our pockets. With the caveat that I haven't fully understood the other answers yet, does this break down on concept or practice / computing power? Sep 14, 2021 at 10:12
• @JohnnyRockex I'm afraid it breaks down on concept. If you want the sum of your row to strongly limit the number of combinations giving rise to the same sum, you need very large numbers. E.g. for each combination to give a unique sum, you cannot use fewer than $n$ bits for the sum (e.g. using the straightforward sequence 1,2,4,8,... so that the sum is simply the binary representation of the bits in that row). Sep 14, 2021 at 10:52
• @JohnnyRockex (continued) As soon as your maximum sum is smaller than that, say 100 bits for $n = 1000$ (for compression by a factor $10/3$), there will be sums that correspond to $2^{1000 - 100} \approx 10^{270}$ combinations. There is no way to identify which one by just mixing values by projection in 3 directions. Sep 14, 2021 at 10:54
• right, so we lose so much information in the sum that we cannot recover it afterwards and accurately say this bit is at that coordinate. If we were to maintain enough identifying coordinate data, the reflection would be uselessly big. Sep 14, 2021 at 12:33

Extrapolating from what you said, using prime numbers will hurt data compression, not help it.

Suppose we have a sequence of 8 bits: ($$b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7$$).

We could make a product of prime numbers to encode that sequence of bits: $$x = 2^{b_0} × 3^{b_1} × 5^{b_2} × 7^{b_3} × 11^{b_4} × 13^{b_5} × 17^{b_6} × 19^{b_7}$$.

But now the range of possible values of $$x$$ is $$[1, 9699690]$$, which would take 24 bits to represent in standard notation. This is far worse than our original 8 bits.

Products of primes can be used for theoretical math proofs though: https://en.wikipedia.org/wiki/G%C3%B6del_numbering

It's a comment, just does not fit

As one of those guys with slow connections, appreciate the efforts.

Youtube is good for me exactly because it has 144p videos, and if something is interesting or I need it I can choose which xxxp to set.

But it has its problems switching and buffering which it probably would not have if that variety of resolutions would be implemented/achieved differently.

In the good old days of modems, it was more often seen, a picture which starts as few huge pixels and then detail'es as long as more data is downloaded. Not sure which compression it was, but it looks like a jpeg on steroids. Those data chunks could be defined as n-streams for video or multiple images, and it could give a finer control on the user side, but setting a limit on how many channels to request, or adjust it automatically.

So maybe take look not in the direction of how much to compress, but how to control quality. All fixed bitrate and variable bitrate compression formats do that varying quality or attempting to keep quality. But they produce one data blob, and manage different resolutions may be challenging on the server-side, so the user does not have that many options (glad there are some places where one has), lags switching quality, etc, etc.

So maybe, as a suggestion, approach the problem from a different perspective -more flexible control of quality on user and server-side. More seamless transition from one quality to another and alike.

People on slower connections already do compromises and sure they appreciate places that offer suitable options. Same way as there is no alternative for youtube for me because the least quality I have seen was 360p and it's top-quality for me (with some difficulties, if weather is right so to speak) if they(alternatives) have such options at all. Sometimes I would not mind 100p or do not need video at all until I do, and when I do, I would like it not to discard the already existing 1min buffer but add to it to improve quality.

So better tools and options and approaches to fight all those compromises may be more appreciated than an amazing algorithm that does 10% better than all existing algorithms on any data. By varying quality I get a 90% reduction of data most of the time - when details begin to be important then yes it's time for heavy guns like waiting for a buffer and other available options.

In general, trading user resources for less data transfer is not impossible, and it is not necessarily purely a math problem - like 5 sentences describing an apple tree or a picture, and user side ai generates one or finds visually similar from a dictionary, etc. But it is a bit more vast problem.

• just noticed .png still has that option of gradual detalization, this image is an example i.stack.imgur.com/fZzVE.png picture with text is not the best use for it but, one I noticed just now. Sep 14, 2021 at 10:20
• That's Adam7 interlacing. Usually, the early passes are rendered as large squares, not single pixels. I've used Adam7 when writing things like fractal explorer programs because it makes it much faster to navigate. Sep 14, 2021 at 22:01