mm-1519 === Subject: ? explicit formula of some special matrices Many numerical analysis for some algorithm solving DEs turn out to be study the eigen system of the discritized system matrix. These matrices have some psecial structures such as banded. Question is, though I searched many numerical books and linear algebra books, I just cannot find one that explicitly shows how to derive the eigenvalues and the eigenvectors of those special matrices. Can anyone suggect a book or show how to derive those? by Cheng Cosine Dec/05/2k4 UT === Subject: Re: Graph Coloring > In any maximal planar graph it is theoretically possible for as many > as three vertices to simultaneously have degree = (n-1). But is seems > that the practical limit is only two vertices. Is it possible to > prove that for all n, there can be only two vertices with degree = > (n-1) in a maximal planar graph? Three vertices with degree n-1, and any three other vertices, would form a K_3,3 subgraph. Therefore the only maximal planar graphs with three degree-(n-1) vertices are those with fewer than three other vertices: that is, K_3, K_4, and the unique 5-vertex maximal planar graph. -- David Eppstein Computer Science Dept., Univ. of California, Irvine http://www.ics.uci.edu/~eppstein/ === Subject: Compare randomness of shuffles - possible? A shuffle of cards is a probability distribution on the permutation group of the cards. What are the methods to compare shuffles in terms of how well they do? For example: randomness? === Subject: Re: Compare randomness of shuffles - possible? Sometime back I was also trying to solve this, and now u have reopened the question in my mind. > A shuffle of cards is a probability distribution on the permutation > group of the cards. What are the methods to compare shuffles in terms > of how well they do? For example: randomness? === Subject: Re: Compare randomness of shuffles - possible? >A shuffle of cards is a probability distribution on the permutation >group of the cards. What are the methods to compare shuffles in terms >of how well they do? For example: randomness? Take the standard deviation of the probabilities of all different permutations. It will be 0 when the probabilities are all equal -- a fair shuffle. --Keith Lewis klewis {at} mitre.org The above may not (yet) represent the opinions of my employer. === Subject: Compare randomness of shuffles - possible? A shuffle of cards is a probability distribution on the permutation group of the cards. What are the methods to compare shuffles in terms of how well they do? For example: randomness? === Subject: Planning in card shuffling To my understanding I suppose a shuffle of cards is a probability distribution on the permutation group of the cards. Given a deck of cards and a number of shuffles is there a method to find a combination of those shuffles that can achieve a certain requirements, for example: A full house on top of the deck with probability greater than a half. === Subject: Re: Planning in card shuffling There's a result called seven shuffles suffice which some mathematician calculated about 10 years ago or so. Based on one model of shuffling, I think they found that seven shuffles would completely randomize the deck by some measure. Kind of the opposite of what you're asking, to unrandomize a deck. Skilled magicians use perfect shuffles for some card tricks: divide the deck exactly in half, and shuffle so that cards from left and right hands alternate exactly. This is NOT a randomizing procedure, and I think it cycles back to the original permutation in four shuffles. - Randy === Subject: Re: Planning in card shuffling > There's a result called seven shuffles suffice which some > mathematician calculated about 10 years ago or so. Based on one model > of shuffling, I think they found that seven shuffles would completely > randomize the deck by some measure. Kind of the opposite of what you're > asking, to unrandomize a deck. > Skilled magicians use perfect shuffles for some card tricks: divide the > deck exactly in half, and shuffle so that cards from left and right > hands alternate exactly. This is NOT a randomizing procedure, and I > think it cycles back to the original permutation in four shuffles. > - Randy You will get back to the original arrangement after executing some number of perfect shuffles, but note that there are two different shuffles here, depending on whether the top card is on top or in second place in the shuffle, as below with 6 cards Original deck: ABCDEF Technique 1 Cut the deck in two: ABC DEF Shuffle the stacks together: ADBECF Technique 2 Cut the deck: ABC DEF Shuffle the stacks together: DAEBFC In this case, technique 1 requires 4 shuffles to get back to the original order and technique 2 requires 3 shuffles. For n = 52, the orders of the two operations are 8 and 52. It's an interesting exercise to find an expression for the orders for general n. Rick === Subject: Re: Planning in card shuffling > To my understanding I suppose a shuffle of cards is a probability > distribution on the permutation group of the cards. Given a deck of > cards and a number of shuffles is there a method to find a combination > of those shuffles that can achieve a certain requirements, for > example: A full house on top of the deck with probability greater than > a half. If you don't have any information about the initial state of the deck, applying a permutation to it's elements (cards) gives nothing better--or as they sometimes say in computer science, garbage in-garbago out. On the other hand, if you have some knowledge about the initial state of the deck, you could use it to obtain rather impressive looking results from your shuffles100% of the time. === Subject: Re: Planning in card shuffling <3LqdnThLjoVeXyncRVn-sA@comcast.com> >about the initial state of the deck Assume the distribution of input is random, output should be like I have to shuffle X times with permutation Y, Z, probability >0.5? === Subject: Computational problem in symmetric group using GAP By using GAP - http://www.gap-system.org/ How can i express a given element in a symmetric group as a product of certain fixed elements in the same symmetric group, if possible by using GAP? Examples of real implementations (by GAP, or Maple?) are mostly welcomed! === Subject: How much lossless compression is possible in images? Assuming ideal compression that removes every trace of redundancy from an image, how much lossless compression might really be possible? I know this is a difficult question because so much depends on image content, but I'm just trying to get an idea of how close current lossless compression methods are to the ideal. Visually images seem to be very highly redundant, although current lossless algorithms only manage about 50% compression. But assuming time and space were not constraints, how far could one theoretically go? -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > Assuming ideal compression that removes every trace of redundancy from > an image, how much lossless compression might really be possible? I > know this is a difficult question because so much depends on image > content, but I'm just trying to get an idea of how close current > lossless compression methods are to the ideal. Visually images seem to > be very highly redundant, although current lossless algorithms only > manage about 50% compression. But assuming time and space were not > constraints, how far could one theoretically go? Time and space are not constraints? Okay then . . . Fix some binary representation x of your image, and some universal Turing machine U. Begin computations of U(0), U(1), U(00), U(01), U(10), and so on up to U(smax) where smax encodes Print x and stop. After BB(n) steps (where n is the number of computations you're running), all the computations that eventually halt will have halted. Now look at the output of all the computations, and pick the (lexigraphically) first string s such that U(s) halted leaving x on the tape. The function BB() is known as the Busy Beaver function. For a typical, say 4 megabyte, image, you'll have to run your computations for about BB(10^10^7) steps. This number is kind of big, and just to compute it is kind of hard. [And Jmes Hrris is kind of unlikely to prove Fermt's Lst Theorem.] The length of the chosen, minimal s is known as the Kolmogorov complexity of x. It is the ultimate measure of how much information is contained in a string, though it is kind of hard to compute in practice. === Subject: Re: How much lossless compression is possible in images? > Time and space are not constraints? Okay then . . . > Fix some binary representation x of your image, and some universal > Turing > machine U. Begin computations of U(0), U(1), U(00), U(01), U(10), and > so > on up to U(smax) where smax encodes Print x and stop. After BB(n) > steps > (where n is the number of computations you're running), all the > computations > that eventually halt will have halted. Now look at the output of all > the > computations, and pick the (lexigraphically) first string s such that > U(s) > halted leaving x on the tape. > The function BB() is known as the Busy Beaver function. For a typical, > say > 4 megabyte, image, you'll have to run your computations for about > BB(10^10^7) > steps. This number is kind of big, and just to compute it is kind of > hard. > [And Jmes Hrris is kind of unlikely to prove Fermt's Lst Theorem.] > The length of the chosen, minimal s is known as the Kolmogorov > complexity of > x. It is the ultimate measure of how much information is contained in > string, though it is kind of hard to compute in practice. So how much compression could you get? -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? >So how much compression could you get? I don't think you have to wait for BB(10^10^7) if you accept a good compression that halts early, given that the ideal algorithm for that image is consise, its a heuristic to expect it to run mostly useful cycles, even on the polynomial side of exponential complexity. Besides you can't tell what BB(x) x>20 is, you have make some heuristic decision when to halt. (of course in your ideal no complexity limits you can tell the value of BB). what compression? on half of the images (99.99999999999% of 4GB images are random pixels) you will get none. the algorithms number to match the data will just be a UTM copy algorithm with the 4GB input string hard wired. Program(487948744894984984 .. 4mb long) = 4 mb image on the other half of images (99.999999999999% of 4GB images are random pixels), you will save a few bytes. of the 0.00000000000001% of images with detail, probably quite good, maybe 10 to 100 times better than jpeg, 10% of original image size for photos. (guess). pictures of cities with intrinsic detail should compress well under a 'selectable algorithm'. Herc === Subject: Re: How much lossless compression is possible in images? what would be interesting about these images if you had the computing technology to do it, is that lossy distortion would be once only. if you decompress a lossy image then compress it again you get the exact image (given that image is a good local minimum of the program sizes to represent it). compare this to jpg, they are terrible to work with, every time you open the image, do a change and save it as jpg the distortion builds up and up. an analogy to digital copies vs analog, once you accept the distortion / approximation of the digitizing process the image will never distort again. Herc === Subject: Re: How much lossless compression is possible in images? > Assuming ideal compression that removes every trace of redundancy from > an image, how much lossless compression might really be possible? I > know this is a difficult question because so much depends on image > content, but I'm just trying to get an idea of how close current > lossless compression methods are to the ideal. Visually images seem to > be very highly redundant, although current lossless algorithms only > manage about 50% compression. But assuming time and space were not > constraints, how far could one theoretically go? > -- > Transpose hotmail and mxsmanic in my e-mail address to reach me directly. It depends totally on image content. An image consisting of random pixels will not compress at all (0% compression) using a generic algorithm; an image consisting of entirely one colour will compress almost to zero (almost 100% compression). A photos maximum compression will vary between 0% and 100% depending upon the amount of random detail in the photo. === Subject: Re: How much lossless compression is possible in images? ... > An image consisting of random pixels will not compress at all (0% > compression) using a generic algorithm; an image consisting of entirely one > colour will compress almost to zero (almost 100% compression). If you use a generic algorithm it is pretty likely that an image consisting of random pixels will expand and not compress. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > If you use a generic algorithm it is pretty likely that an image consisting > of random pixels will expand and not compress. Actually, the chance that a random image will become smaller after compression with any given algorithm is always 0.5. The change that it will become larger is thus also 0.5. Half of all random images will be smaller; the other half will be larger. This is true no matter what algorithm is used, as long as it is lossless (reversible). -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > If you use a generic algorithm it is pretty likely that an image consisting > of random pixels will expand and not compress. > Actually, the chance that a random image will become smaller after > compression with any given algorithm is always 0.5. The change that it > will become larger is thus also 0.5. Half of all random images will be > smaller; the other half will be larger. This is true no matter what > algorithm is used, as long as it is lossless (reversible). Wrong, see my other reply. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? Originator: richard@cogsci.ed.ac.uk (Richard Tobin) >Actually, the chance that a random image will become smaller after >compression with any given algorithm is always 0.5. Why? Consider the algorithm that precedes all input strings with a 1-bit. It makes all strings longer. Perhaps you don't consider that a compression algorithm. So now consider the algorithm that replaces all strings starting with a sequence of ten or more zeros with a byte count of the zeros (up to 255) followed by the rest of the string, and the other strings with a 0 byte followed by the original string. That only make 1 in 1024 strings smaller. So maybe you mean an algorithm that, on average, doesn't change the length (which is the best kind of algorithm). Maybe it makes one very long string small, and lots of others just lightly bigger. This will obviously not make 50% of images smaller. -- Richard === Subject: Re: How much lossless compression is possible in images? > Why? Because compression only works if some messages of a given length are more probable than others of that same length. If messages are completely random, they are all equally probable. And if random messages must be preserved bit-by-bit, it is not possible to represent them with fewer bits than they originally contained. The entropy of the messages must be preserved. > Consider the algorithm that precedes all input strings with a 1-bit. > It makes all strings longer. This isn't really a compression algorithm in the sense being discussed here. A compression algorithm is simply a substitution algorithm. It performs a one-for-one substitution of variable-length messages from one set A for fixed-length messages from another set B. Set A is designed such that the messages it contains corresponding to the most probable messages in B are shorter than the fixed-length of the messages in B; all other messages in A are longer. Since the most probable messages in B are translated to shorter messages in A, the algorithm effectively compresses messages. But this only works if the messages in B are not all equally probable. If they are equally probable (as they must be if they are random), there is no way to compress them, because a longer message from A is just as likely to be substituted as a shorter message. Note that the total length of all messages in set A must be at least equal to the total length of all messages in set B. So if random substitution of messages from A is forced by equal probability for all messages from B (random messages in B), then the net result is zero compression. > Perhaps you don't consider that a compression algorithm. I don't. A more rigorous definition can be found above. > So maybe you mean an algorithm that, on average, doesn't change the > length (which is the best kind of algorithm). All algorithms will produce output of equal or greater length than input if the input is random. > Maybe it makes one > very long string small, and lots of others just lightly bigger. This > will obviously not make 50% of images smaller. It will, however, guarantee that the average length change for all messages is zero, which is nearly the same thing from a practical standpoint. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > It depends totally on image content. > An image consisting of random pixels will not compress at all (0% > compression) using a generic algorithm; an image consisting of entirely one > colour will compress almost to zero (almost 100% compression). > A photos maximum compression will vary between 0% and 100% depending upon > the amount of random detail in the photo. My understanding has been that a Fourier transformation can greatly compress data, but that the best compression is achieved by analyzing and compressing the entire data set as a single unit, which is impractical in real life because it's computationally very difficult to analyze, say, an entire 400 MB of image data and produce a single transformation encompassing that entire file. If it were done, though, I presume it would be very compact indeed. Can anyone confirm this? I know that some existing systems also allow for a bit of image-dependent customization, but that it often isn't carried out because of the overhead. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> gif uses run length encode r r r r -> 4r so its only suitable for a low color pallete jpg fourier transforms the image, then uses run length encode on that. often the final digits of each row are 0's, these are the high frequencies (the detail) and compression just ignores some of them. if you only chop 0's you get lossless compression, if you chop 00002000030001000 it gets lossy. quadtree is a recursive subdividing algorithm that could be useful for maps but never took off. i devised a composite quadtree gif system. the quadtree seperates the image into discernible simple sections, and the run length encode is tested at 360 different angles to find the best compression. basically it searches for line segments, suitable for vector type graphics, stickmen. what gets me is why they can't add a pollish function to jpeg decompression, obviously a big single color area with a border edge around it is not meant to get 'pixelated' at the border. apparently there is a fractal equation for every photo in existence. some amazing pictures of womens faces were constructed with equations (very high compression) if you can tailor the image somewhat. and the detail just keeps up as you zoom in.. computer games cheat, they store a library of tile bitmaps and surface everything, why download when you can put in a DVD of a million pictures and the computer just selects. Herc === Subject: Re: How much lossless compression is possible in images? > gif uses run length encode > r r r r -> 4r Wrong. Gif uses LZW. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? >> gif uses run length encode >> r r r r -> 4r >Wrong. Gif uses LZW. right, actually its selectable. Herc === Subject: Re: How much lossless compression is possible in images? >> gif uses run length encode >> >> r r r r -> 4r > >Wrong. Gif uses LZW. > right, actually its selectable. Wrong, it is not selectable, at least not in Gif89a, and as far as I know that is the last version ever published. If it were selectable there would have been a plethora of free Gif builders that used only RLE. But because Gif builders use LZW they fall under a patent and are not free to use (decoders for LZW *are* free to use). That is also the reason the W3 consortium has defined a new format: PNG. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > But because Gif builders use LZW they fall under a patent and are not free > to use (decoders for LZW *are* free to use). The patent has expired. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > But because Gif builders use LZW they fall under a patent and are not free > to use (decoders for LZW *are* free to use). > The patent has expired. I think it is too late. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > I think it is too late. Too late for what? It's too late to file any patent-infringement claims, yes--since the patent has expired. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > I think it is too late. > Too late for what? It's too late to file any patent-infringement > claims, yes--since the patent has expired. Too late to see a plethora of free gif encoders emerging. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: `Uncompressed' GIF files (was: Re: How much lossless compression is possible in images?) Originator: dmoews@ccrwest.org (David Moews) |[...] |Wrong, it is not selectable, at least not in Gif89a, and as far as I know |that is the last version ever published. If it were selectable there |would have been a plethora of free Gif builders that used only RLE. But |because Gif builders use LZW they fall under a patent and are not free |to use (decoders for LZW *are* free to use). That is also the reason the |W3 consortium has defined a new format: PNG. Although the GIF format specifies the use of an LZW decompressor, it is possible to write GIF files which, although readable by an LZW decompressor, are not actually compressed. Presumably, this does not infringe on LZW patents. This is the approach used by the developers of libungif . -- David Moews dmoews@xraysgi.ims.uconn.edu === Subject: Re: `Uncompressed' GIF files (was: Re: How much lossless compression is possible in images?) > |[...] > |Wrong, it is not selectable, at least not in Gif89a, and as far as I know > |that is the last version ever published. > Although the GIF format specifies the use of an LZW decompressor, it is > possible to write GIF files which, although readable by an LZW decompressor, > are not actually compressed. Oh, yes, that is very true. When you know enough about the LZW format and the actual format used, it is possible to present files that are not LZW compresses, but are still readable by a GIF/LZW decompressor. LZ compressions are pretty similar, there is only a slight variation. Standard LZ uses pointers back into previous material, and it is only a variation on how it is presented and how long the previous material is. LZW is only a slight change in that it uses a dictionary of previous material. The way how the dictionary is build, and the way how it is decided that the current dictionary is full, are part of the patent. If you have other ways to build a dictionary (and a way to encode it that can be understood by LZW decompressors), there is no patent infringement. I can imagine a few ways. And Eric Raymond is also not entirely stupid... But, RLE encoding is not decompressible by LZW decoders as far as I know. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? www.justsaying.com/rle.gif Gods don't make mistakes! Herc === Subject: Re: How much lossless compression is possible in images? > www.justsaying.com/rle.gif > Gods don't make mistakes! a. Description. The image data for a table based image consists of a sequence of sub-blocks, of size at most 255 bytes each, containing an index into the active color table, for each pixel in the image. Pixel indices are in order of left to right and from top to bottom. Each index must be within the range of the size of the active color table, starting at 0. The sequence of indices is encoded using the LZW Algorithm with variable-length code, as described in Appendix F. And see also Appendix F of that document. But I will look what your gif file amounts to. I suspect it will be a form of LZW. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > > www.justsaying.com/rle.gif > > > > Gods don't make mistakes! > a. Description. The image data for a table based image consists of a > sequence of sub-blocks, of size at most 255 bytes each, containing an > index into the active color table, for each pixel in the image. Pixel > indices are in order of left to right and from top to bottom. Each index > must be within the range of the size of the active color table, starting > at 0. The sequence of indices is encoded using the LZW Algorithm with > variable-length code, as described in Appendix F. > And see also Appendix F of that document. But I will look what your gif > file amounts to. I suspect it will be a form of LZW. The LZW patent has expired. === Subject: Re: How much lossless compression is possible in images? >But I will look what your gif >file amounts to. I suspect it will be a form of >LZW. >dik t. winter http://www.justsaying.com/rle.gif http://www.justsaying.com/lzw.gif here's 2 gifs with the same original image, simple checkers. Herc === Subject: Re: How much lossless compression is possible in images? > Assuming ideal compression that removes every trace of redundancy from > an image, how much lossless compression might really be possible? I > know this is a difficult question because so much depends on image > content, but I'm just trying to get an idea of how close current > lossless compression methods are to the ideal. Visually images seem to > be very highly redundant, although current lossless algorithms only > manage about 50% compression. But assuming time and space were not > constraints, how far could one theoretically go? > -- > Transpose hotmail and mxsmanic in my e-mail address to reach me directly. > It depends totally on image content. > An image consisting of random pixels will not compress at all (0% > compression) using a generic algorithm; an image consisting of entirely one > colour will compress almost to zero (almost 100% compression). I don't have the math at hand, but I believe that a truly random image would have at least some compressible areas. In a strange sense, a completely incompressible image would be as ordered as a single color image. === Subject: Re: How much lossless compression is possible in images? >> Assuming ideal compression that removes every trace of redundancy from >> an image, how much lossless compression might really be possible? I >> know this is a difficult question because so much depends on image >> content, but I'm just trying to get an idea of how close current >> lossless compression methods are to the ideal. Visually images seem to >> be very highly redundant, although current lossless algorithms only >> manage about 50% compression. But assuming time and space were not >> constraints, how far could one theoretically go? >> >> -- >> Transpose hotmail and mxsmanic in my e-mail address to reach me >directly. >> It depends totally on image content. >> An image consisting of random pixels will not compress at all (0% >> compression) using a generic algorithm; an image consisting of entirely >one >> colour will compress almost to zero (almost 100% compression). >I don't have the math at hand, but I believe that a truly random image >would have at least some compressible areas. In a strange sense, a >completely incompressible image would be as ordered as a single color image. There's no such thing as an incompressible image, _until_ you specify what algorithm you're using. Given _any_ image I_0 there _is_ a lossless compression algorithm that compresses I_0 to a one-byte file: def compress(I): if I == I_0: return a single 0 byte else: return a 1, followed by I. I leave the decompressor as an exercise. ************************ David C. Ullrich === Subject: Re: How much lossless compression is possible in images? > There's no such thing as an incompressible image, _until_ you specify > what algorithm you're using. Given _any_ image I_0 there _is_ a > lossless compression algorithm that compresses I_0 to a one-byte file: > def compress(I): > if I == I_0: > return a single 0 byte > else: > return a 1, followed by I. > I leave the decompressor as an exercise. Your example also highlights a point about how the effectiveness of compression is to be measured. Since the *decompressor* is essential to recovering the original image from the output of the compressor, istm that an appropriate measure ought to include the size of the decompressor as well as the size of the compressor output. E.g., if we use the simple ratio r = (|image_compressed| + |decompressor|) / |image_original| , then of course your example has r > 1, rather than the desired r < 1. With that in mind, it might make sense to speak of an image as being absolutely incompressible if all compressors & decompressors have r >= 1 for that image. --r.e.s. === Subject: Re: How much lossless compression is possible in images? >> There's no such thing as an incompressible image, _until_ you specify >> what algorithm you're using. Given _any_ image I_0 there _is_ a >> lossless compression algorithm that compresses I_0 to a one-byte file: >> def compress(I): >> if I == I_0: >> return a single 0 byte >> else: >> return a 1, followed by I. >> I leave the decompressor as an exercise. >Your example also highlights a point about how the effectiveness of >compression is to be measured. Since the *decompressor* is essential >to recovering the original image from the output of the compressor, >istm that an appropriate measure ought to include the size of the >decompressor as well as the size of the compressor output. >E.g., if we use the simple ratio >r = (|image_compressed| + |decompressor|) / |image_original| , >then of course your example has r > 1, rather than the desired r < 1. >With that in mind, it might make sense to speak of an image as being >absolutely incompressible if all compressors & decompressors have >r >= 1 for that image. Nope. The length of the code for a decompressor depends on what language we're using. See my reply to guenther's reply to Tobin for a more detailed explanation. >--r.e.s. ************************ David C. Ullrich === Subject: Re: How much lossless compression is possible in images? >>Your example also highlights a point about how the effectiveness of >>compression is to be measured. Since the *decompressor* is essential >>to recovering the original image from the output of the compressor, >>istm that an appropriate measure ought to include the size of the >>decompressor as well as the size of the compressor output. >>E.g., if we use the simple ratio >>r = (|image_compressed| + |decompressor|) / |image_original| , >>then of course your example has r > 1, rather than the desired r < 1. >>With that in mind, it might make sense to speak of an image as being >>absolutely incompressible if all compressors & decompressors have >>r >= 1 for that image. > Nope. The length of the code for a decompressor depends on what > language we're using. See my reply to guenther's reply to Tobin > for a more detailed explanation. Interpret all compressors & decompressors more inclusively, please. --r.e.s. === Subject: Re: How much lossless compression is possible in images? >Your example also highlights a point about how the effectiveness of >compression is to be measured. Since the *decompressor* is essential >to recovering the original image from the output of the compressor, >istm that an appropriate measure ought to include the size of the >decompressor as well as the size of the compressor output. >E.g., if we use the simple ratio >r = (|image_compressed| + |decompressor|) / |image_original| , >then of course your example has r > 1, rather than the desired r < 1. >With that in mind, it might make sense to speak of an image as being >absolutely incompressible if all compressors & decompressors have >r >= 1 for that image. >> Nope. The length of the code for a decompressor depends on what >> language we're using. See my reply to guenther's reply to Tobin >> for a more detailed explanation. >Interpret all compressors & decompressors more inclusively, please. Huh? That's what I thought I was doing. _If_ we interpret it _less_ inclusively, restricting to one particular language, then what you said is right. But if we interpret it more inclusively, allowing any programming language, then there are no absolutely incompressible images by the definition above. >--r.e.s. ************************ David C. Ullrich === Subject: Re: How much lossless compression is possible in images? >>Your example also highlights a point about how the effectiveness of >>compression is to be measured. Since the *decompressor* is essential >>to recovering the original image from the output of the compressor, >>istm that an appropriate measure ought to include the size of the >>decompressor as well as the size of the compressor output. >> >>E.g., if we use the simple ratio >>r = (|image_compressed| + |decompressor|) / |image_original| , >>then of course your example has r > 1, rather than the desired r < 1. >> >>With that in mind, it might make sense to speak of an image as being >>absolutely incompressible if all compressors & decompressors have >>r >= 1 for that image. > > Nope. The length of the code for a decompressor depends on what > language we're using. See my reply to guenther's reply to Tobin > for a more detailed explanation. >>Interpret all compressors & decompressors more inclusively, please. > Huh? That's what I thought I was doing. > _If_ we interpret it _less_ inclusively, restricting to one > particular language, then what you said is right. But if > we interpret it more inclusively, allowing any programming > language, then there are no absolutely incompressible > images by the definition above. I don't care for the expression, but ... huh? The statement above, which I said might be true, is of the form S(x) = P, if Q(x) holds for all x in set B. In one case, B is the set A_L of all compressors & decompressors in language L, and in the other case B is the union of all the A_L; and I call the union more inclusive than any one of its subsets A_L. If S(x) is true when B is A, but not true when B is one of the A_L, then I would say it's true for the more inclusive set, wouldn't you? (The irony here is that I agree with what you say, otherwise; it would have better if I'd made the language issue explicit.) --r.e.s. === Subject: Re: How much lossless compression is possible in images? > There's no such thing as an incompressible image, _until_ you specify > what algorithm you're using. Given _any_ image I_0 there _is_ a > lossless compression algorithm that compresses I_0 to a one-byte file: > def compress(I): > if I == I_0: > return a single 0 byte > else: > return a 1, followed by I. > I leave the decompressor as an exercise. You can even do that with 255 images I_1 through I_255: def compress(I): if I = I_1: return a single 1 byte if I = I_2: return a single 2 byte ... if I = I_255: return a single 255 byte else: return a 0, followed by I -- Daniel W. Johnson panoptes@iquest.net http://members.iquest.net/~panoptes/ 039 53 36 N / 086 11 55 W === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <2of8r05du90qm548kmv6924elsqifm6pjr@4ax.com> message >> >> Assuming ideal compression that removes every trace of redundancy from >> an image, how much lossless compression might really be possible? I >> know this is a difficult question because so much depends on image >> content, but I'm just trying to get an idea of how close current >> lossless compression methods are to the ideal. Visually images seem to >> be very highly redundant, although current lossless algorithms only >> manage about 50% compression. But assuming time and space were not >> constraints, how far could one theoretically go? >> >> -- >> Transpose hotmail and mxsmanic in my e-mail address to reach me >directly. >> >> It depends totally on image content. >> >> An image consisting of random pixels will not compress at all (0% >> compression) using a generic algorithm; an image consisting of entirely >one >> colour will compress almost to zero (almost 100% compression). >I don't have the math at hand, but I believe that a truly random image >would have at least some compressible areas. In a strange sense, a >completely incompressible image would be as ordered as a single color image. > There's no such thing as an incompressible image, _until_ you specify You are joking Ullrich, are you not? It is amazing that a professional mathematician should utter such nonsense. There are binary strings which are not compressible under any circumstances. > what algorithm you're using. Given _any_ image I_0 there _is_ a > lossless compression algorithm that compresses I_0 to a one-byte file: > def compress(I): > if I == I_0: > return a single 0 byte > else: > return a 1, followed by I. > I leave the decompressor as an exercise. No Ullrich, you provide the decompressor. In trying seriously you will realise the humbling dimension of your blunder. > ************************ > David C. Ullrich === Subject: Re: How much lossless compression is possible in images? > You are joking Ullrich, are you not? It is amazing that a professional > mathematician should utter such nonsense. There are binary strings > which are not compressible under any circumstances. There are no such strings. It is always possible to devise an algorithm that compresses a given string, no matter what the pattern of bits. It's easy to do. If c is the specific string you wish to compress, then you define your algorithm such that 1 represents c, and 0 followed by m represents any other string m. This can be done for any arbitrary c. QED. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? Originator: richard@cogsci.ed.ac.uk (Richard Tobin) >> You are joking Ullrich, are you not? It is amazing that a professional >> mathematician should utter such nonsense. There are binary strings >> which are not compressible under any circumstances. >There are no such strings. It is always possible to devise an algorithm >that compresses a given string, no matter what the pattern of bits. Probably he's thinking of single-bit strings, which can't be compressed. But that's just pedantry. -- Richard === Subject: Re: How much lossless compression is possible in images? Originator: richard@cogsci.ed.ac.uk (Richard Tobin) >You are joking Ullrich, are you not? It is amazing that a professional >mathematician should utter such nonsense. There are binary strings >which are not compressible under any circumstances. Suppose B is such a string, with length > 1 bit. Consider the compression algorithm which encodes B as a single 1 bit, and all other strings as 0 followed by the string. This algorithm compresses the allegedly incompressible string. -- Richard === Subject: Re: How much lossless compression is possible in images? <2of8r05du90qm548kmv6924elsqifm6pjr@4ax.com> Unfortunately Tobin, to talk about compression is meaningless if you do not specify how the length of the decompressor is included in the measurement of compression. Simply stating that pumpernikel is the compressed representation of Moby Dyck is a joke, not an algorithm. Things are only interesting if you can transmit pumpernikel and the decoding instructions at a lesser cost than transmitting the whole text of Moby Dyck. === Subject: Re: How much lossless compression is possible in images? > Unfortunately Tobin, to talk about compression is meaningless if you do > not specify how the length of the decompressor is included in the > measurement of compression. Simply stating that pumpernikel is the > compressed representation of Moby Dyck is a joke, not an algorithm. > Things are only interesting if you can transmit pumpernikel and the > decoding instructions at a lesser cost than transmitting the whole text > of Moby Dyck. The length of a compression algorithm designed to compress only one specific message to a single bit (maximal compression) will always be at least as long as the message being compressed. Since it provides compression for no other message, it can only be used once, which means that the length of the compressed message is effectively one bit plus the length of the algorithm. However, in more practical real-world scenarios, this situation does not obtain. An algorithm need only be communicated once. It may be able to significantly compress a vast number of messages. Dividing the length of the algorithm by the total volume of message data that it can compress may well cause it to shrink into insignificance. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <2of8r05du90qm548kmv6924elsqifm6pjr@4ax.com> <9v6cr09pcllb26tn5n6q8g8tsfitdrq8i7@4ax.com> Discussion, linux) > The length of a compression algorithm designed to compress only one > specific message to a single bit (maximal compression) will always be at > least as long as the message being compressed. That depends on your programming language. Nothing prevents me from using a formalism for Turing machines that assigns to the program outputting Moby Dick the index 0. You have to fix a formalism before really discussing compression. Even then, there's no reason your above claim is true. In fact, it can be false through means other than the cheap trick I use above. Consider the algorithm that maps the string 000...0 (5000 zeros) the code 0 and every other string prepends 1. The decoder can be very short indeed. It doesn't have to be 5000 bits long. -- Jesse F. Hughes I may have invented it, but Bill [Gates] made it famous. -- David Bradley, inventor of the Ctrl-Alt-Del reboot sequence === Subject: Re: How much lossless compression is possible in images? > Consider the algorithm that maps the string 000...0 (5000 zeros) > the code 0 and every other string prepends 1. The decoder can be > very short indeed. It doesn't have to be 5000 bits long. Such an algorithm wouldn't work for _any_ given string, but only for a string of zeros. I'm thinking of an algorithm optimized to compress a single, specific string maximally, without any regard for the actual bit pattern of the string. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <2of8r05du90qm548kmv6924elsqifm6pjr@4ax.com> <9v6cr09pcllb26tn5n6q8g8tsfitdrq8i7@4ax.com> <87vfbdx9ee.fsf@phiwumbda.org> Discussion, linux) >> Consider the algorithm that maps the string 000...0 (5000 zeros) >> the code 0 and every other string prepends 1. The decoder can be >> very short indeed. It doesn't have to be 5000 bits long. > Such an algorithm wouldn't work for _any_ given string, but only for a > string of zeros. I'm thinking of an algorithm optimized to compress a > single, specific string maximally, without any regard for the actual bit > pattern of the string. To which my other comments apply. You have to fix an encoding of Turing machines before any of this makes much sense. There's no reason I can't choose an encoding so that the machine which outputs Moby Dick is given index 0. -- By initially making it virtually impossible to maintain a heterogenous environment of Word 95 and Word 97 systems, Microsoft offered its customers that most eloquent of arguments for upgrading: the delicate sound of a revolver being cocked somewhere just out of sight. --Dan Martinez === Subject: Re: How much lossless compression is possible in images? > The length of a compression algorithm designed to compress only one > specific message to a single bit (maximal compression) will always be at > least as long as the message being compressed. Please enlighten me. Why would maximal compression be to a single bit? Will that bit turn out to be a 0, or a 1? If it matters, why not add it to the compression algorithm? If it doesn't matter, why have it at all? -- Alec McKenzie === Subject: Re: How much lossless compression is possible in images? > The length of a compression algorithm designed to compress only one > specific message to a single bit (maximal compression) will always be at > least as long as the message being compressed. > Please enlighten me. Why would maximal compression be to a single bit? That's the shortest possible output string. > Will that bit turn out to be a 0, or a 1? It doesn't matter. > If it matters, why not add it to the compression algorithm? > If it doesn't matter, why have it at all? I don't understand these questions. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > Unfortunately Tobin, to talk about compression is meaningless if you do > not specify how the length of the decompressor is included in the > measurement of compression. Simply stating that pumpernikel is the > compressed representation of Moby Dyck is a joke, not an algorithm. > Things are only interesting if you can transmit pumpernikel and the > decoding instructions at a lesser cost than transmitting the whole text > of Moby Dyck. Ever heard of commercial telegraph codes? They weren't ever used for anything quite that dramatic, but there was some savings based on having sent the decoding instructions physically at a slower pace (perhaps in the luggage of the employee being relocated). -- Daniel W. Johnson panoptes@iquest.net http://members.iquest.net/~panoptes/ 039 53 36 N / 086 11 55 W === Subject: Re: How much lossless compression is possible in images? >Unfortunately Tobin, to talk about compression is meaningless if you do >not specify how the length of the decompressor is included in the >measurement of compression. Simply stating that pumpernikel is the >compressed representation of Moby Dyck is a joke, not an algorithm. >Things are only interesting if you can transmit pumpernikel and the >decoding instructions at a lesser cost than transmitting the whole text >of Moby Dyck. Well, there's no point in trying to explain why this is specious to guenther, because he already Knows the Truth. For anyone else who's curious why this is not a valid objection: It's _impossible_ to include a _complete_ specification of the decompressor in _any_ compressed file. Say we include C code for the compressor. That code is meaningless unless we know in advance that it's C code, and know in advance how C code is to be interpreted. So we have to include the C specification in the file. But the C spec is written in English - it will be meaningless to someone who doesn't know English (and worse, it _could_ happen that the English specifying how to write a C compiler just _happens_ to be meaningful but mean something totally different in Martian.) So we need to include a specification of what all the English words mean. In what language shall that definition of the English language be written? Etc. It's impossible to define everything in terms of previously defined terms - _any_ communication relies on an _assumption_ that there is some common language, which assumption is impossible to actually verify. In practice we're not required to include the C specification, we're allowed to _assume_ that the user will know that the code for the decompressor is C and that he has a C compiler already. But allowing this assumption, while not allowing the assumption that the user knows the text of Moby Dick, is purely arbitrary - there's no objective way to draw the line mathematically. And if we assume that the user is using a language exactly like C, except that Moby_Dick expands to the text of Moby Dick, then transmitting pumpernikel along with the code for the decompressor is much more efficient than transmitting the complete text. ************************ David C. Ullrich === Subject: Re: How much lossless compression is possible in images? >> >message > > Assuming ideal compression that removes every trace of >redundancy from > an image, how much lossless compression might really be >possible? I > know this is a difficult question because so much depends on >image > content, but I'm just trying to get an idea of how close current > lossless compression methods are to the ideal. Visually images >seem to > be very highly redundant, although current lossless algorithms >only > manage about 50% compression. But assuming time and space were >not > constraints, how far could one theoretically go? > > -- > Transpose hotmail and mxsmanic in my e-mail address to reach me >>directly. > > It depends totally on image content. > > An image consisting of random pixels will not compress at all (0% > compression) using a generic algorithm; an image consisting of >entirely >>one > colour will compress almost to zero (almost 100% compression). >> >>I don't have the math at hand, but I believe that a truly random >image >>would have at least some compressible areas. In a strange sense, a >>completely incompressible image would be as ordered as a single >color image. >> There's no such thing as an incompressible image, _until_ you specify >You are joking Ullrich, are you not? It is amazing that a professional >mathematician should utter such nonsense. There are binary strings >which are not compressible under any circumstances. >> what algorithm you're using. Given _any_ image I_0 there _is_ a >> lossless compression algorithm that compresses I_0 to a one-byte >file: >> def compress(I): >> if I == I_0: >> return a single 0 byte >> else: >> return a 1, followed by I. >> I leave the decompressor as an exercise. >No Ullrich, you provide the decompressor. In trying seriously you will >realise the humbling dimension of your blunder. Um, in case _you're_ not joking: def decompress(data): if data == '0': return I_0 else: return data with first byte omitted >> ************************ >> David C. Ullrich David C. Ullrich === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <2of8r05du90qm548kmv6924elsqifm6pjr@4ax.com> >> >> There's no such thing as an incompressible image, _until_ you specify >You are joking Ullrich, are you not? It is amazing that a professional >mathematician should utter such nonsense. There are binary strings >which are not compressible under any circumstances. >> what algorithm you're using. Given _any_ image I_0 there _is_ a >> lossless compression algorithm that compresses I_0 to a one-byte >file: >> >> def compress(I): >> if I == I_0: >> return a single 0 byte >> else: >> return a 1, followed by I. >> >> I leave the decompressor as an exercise. >No Ullrich, you provide the decompressor. In trying seriously you will >realise the humbling dimension of your blunder. > Um, in case _you're_ not joking: > def decompress(data): > if data == '0': > return I_0 > else: > return data with first byte omitted >> ************************ >> >> David C. Ullrich > David C. Ullrich You are not trying seriously Ullrich. You have not even started to define what you mean by compressing. If you care to check the literature, you will find that compression is said to have taken place when the representation of both the decompressing algorithm and the output are of lesser total length than the input. Apart from that, your construction fails for the input '0' since it does not compress it under any definition of compression you might wish to choose, therefore your statement is wrong in any case. === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <2of8r05du90qm548kmv6924elsqifm6pjr@4ax.com> >> >> There's no such thing as an incompressible image, _until_ you specify >You are joking Ullrich, are you not? It is amazing that a professional >mathematician should utter such nonsense. There are binary strings >which are not compressible under any circumstances. >> what algorithm you're using. Given _any_ image I_0 there _is_ a >> lossless compression algorithm that compresses I_0 to a one-byte >file: >> >> def compress(I): >> if I == I_0: >> return a single 0 byte >> else: >> return a 1, followed by I. >> >> I leave the decompressor as an exercise. >No Ullrich, you provide the decompressor. In trying seriously you will >realise the humbling dimension of your blunder. > Um, in case _you're_ not joking: > def decompress(data): > if data == '0': > return I_0 > else: > return data with first byte omitted >> ************************ >> >> David C. Ullrich > David C. Ullrich You are not trying seriously Ullrich. You have not even started to define what you mean by compressing. If you care to check the literature, you will find that compression is said to have taken place when the representation of both the decompressing algorithm and the output are of lesser total length than the input. Apart from that, your construction fails for the input '0' since it does not compress it under any definition of compression you might wish to choose, therefore your statement is wrong in any case. === Subject: Re: How much lossless compression is possible in images? > You are not trying seriously Ullrich. You have not even started to > define what you mean by compressing. If you care to check the > literature, you will find that compression is said to have taken place > when the representation of both the decompressing algorithm and the > output are of lesser total length than the input. Said by whom? You're not compressing algorithms, you're compressing messages. If you want to include the length of the algorithm, then you must include it with the cumulative lengths of all possible messages, not just one message. And in that case, there obviously will always be an increase in size ... because random data cannot be compressed. A compression algorithm in this sense always increases redundancy. But in practice you don't write an algorithm for all possible messages, but only for certain, highly probable messages, and in this specific case the total length is greatly reduced, even with the length of the algorithm. So compression occurs. Since compression is meaningless if all messages are equally probable (and thus random), one must assume that some subset of all possible messages are more probable than others when discussing any type of compression. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <2of8r05du90qm548kmv6924elsqifm6pjr@4ax.com> > Said by whom? You're not compressing algorithms, you're compressing > messages. Here's a challenge for you. You have to stay inside your home for a week. Throw away anything edible. Now write down an order for the food you will eat during that week. Now call at the grocer's. According to your bull there is an algorithm whicht codifies that order into the word Rumpelstilskin. You may only pronounce the word Rumpelstilskin once into the phone and must then hang up. Now sit and wait for your delivery. ËAlready hungry? Hint: the decoding instructions, or the definition for the encoding, are part of the message. Exceptions to this rule in real life practical use are of no interest to theory. === Subject: Re: How much lossless compression is possible in images? > Hint: the decoding instructions, or the definition for the encoding, > are part of the message. No. If the definiton of the encoding is part of the message, then the only way to know how the message is to be decoded is to decode the message, which means that no communication via messages is possible at all. In fact, the encoding method is know by both ends of a communication channel before any messages are exchanged. Otherwise no communication of information can take place--all signals exchanged over the channel are noise. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? >Here's a challenge for you. You have to stay inside your home for a >week. Throw away anything edible. Now write down an order for the food >you will eat during that week. Now call at the grocer's. According to >your bull there is an algorithm whicht codifies that order into the >word Rumpelstilskin. You may only pronounce the word >Rumpelstilskin once into the phone and must then hang up. Now sit and >wait for your delivery. =BFAlready hungry? >Hint: the decoding instructions, or the definition for the encoding, >are part of the message. Exceptions to this rule in real life practical >use are of no interest to theory. So perfectly compressed messages are perfectly encrypted? Rich === Subject: Re: How much lossless compression is possible in images? >Here's a challenge for you. You have to stay inside your home for a >week. Throw away anything edible. Now write down an order for the food >you will eat during that week. Now call at the grocer's. According to >your bull there is an algorithm whicht codifies that order into the >word Rumpelstilskin. You may only pronounce the word >Rumpelstilskin once into the phone and must then hang up. Now sit and >wait for your delivery. =BFAlready hungry? >Hint: the decoding instructions, or the definition for the encoding, >are part of the message. Exceptions to this rule in real life practical >use are of no interest to theory. > So perfectly compressed messages are perfectly encrypted? > Rich Not as far as I understand. Good encryption requires that it be unbreakable even if the algorithm used is known to an attacker. On the other hand, well encrypted strings should be incompressible because they should be devoid of any statistical features, which are considered weaknesess in cryptology. === Subject: Re: How much lossless compression is possible in images? >> >>Here's a challenge for you. You have to stay inside your home for a >>week. Throw away anything edible. Now write down an order for the >food >>you will eat during that week. Now call at the grocer's. According >>your bull there is an algorithm whicht codifies that order into >the >>word Rumpelstilskin. You may only pronounce the word >>Rumpelstilskin once into the phone and must then hang up. Now sit >and >>wait for your delivery. =BFAlready hungry? >> >>Hint: the decoding instructions, or the definition for the encoding, >>are part of the message. Exceptions to this rule in real life >practical >>use are of no interest to theory. >> >> So perfectly compressed messages are perfectly encrypted? >Not as far as I understand. Good encryption requires that it be >unbreakable even if the algorithm used is known to an attacker. On the >other hand, well encrypted strings should be incompressible because >they should be devoid of any statistical features, which are considered >weaknesess in cryptology. Yes. This is my understanding as well. What confuses me is that I understood your post about ordering food to imply that some *imperfectly* compressed messages are perfectly encrypted! How can this be? Rich === Subject: Re: How much lossless compression is possible in images? >> >>Here's a challenge for you. You have to stay inside your home for a >>week. Throw away anything edible. Now write down an order for the >food >>you will eat during that week. Now call at the grocer's. According >to >>your bull there is an algorithm whicht codifies that order into >the >>word Rumpelstilskin. You may only pronounce the word >>Rumpelstilskin once into the phone and must then hang up. Now sit >and >>wait for your delivery. =BFAlready hungry? >> >>Hint: the decoding instructions, or the definition for the encoding, >>are part of the message. Exceptions to this rule in real life >practical >>use are of no interest to theory. >> >> >> So perfectly compressed messages are perfectly encrypted? >> >Not as far as I understand. Good encryption requires that it be >unbreakable even if the algorithm used is known to an attacker. On the >other hand, well encrypted strings should be incompressible because >they should be devoid of any statistical features, which are considered >weaknesess in cryptology. > Yes. This is my understanding as well. What confuses me is that I understood > your post about ordering food to imply that some *imperfectly* compressed > messages are perfectly encrypted! How can this be? > Rich Well, then you got it wrong. My challenge had nothing to do with either perfection of compression nor with encryption in any form. Mr. OP here keeps babbling that for any given string an algorithm can be deviced which will compress it. That statement can only be upheld under the assumption that the decompressor has not to be accounted for in any way in the process of meassuring the compression rate. Unfortunately any discussion based on such an assumption is nothing but contemptible prattle. The story with the grocery order is just an attempt at and creates an algorithm that will compress it. Then, he compresses the order and transmits the output to the grocer. The grocer, let's call him Mr. Li is in the very unfortunate situation that he cannot even start guessing at the meaning of the message. Even if he knows beforehand that Mr. M is a crank reputed for his pecularity and always compresses his messages with freshly and specially devised algorithms he has absolutely no clue as to what algorithm was applied (remember that the algorithm has most recently been invented by Mr. M for this ocassion). Therefore he has zero possibilities of decoding the message. As a result of this situation Mr. M will be one ravenous crackpot during the following week. There are only two possibilities for the resolution of the problem a) Mr Li always knows in advance what Mr. M will order, b) Mr. M transmits along with the output of his compressor, the essential information required by Mr. Li in the process of decoding. In case a) the processes of compressing and transmitting the information are superfluous a circumstance which makes a discussion of compressibility nothing but contemptible prattling. Case b) the interesting one, denies the OP's ridiculous musings. I would point out to you that there are no further cases, and that the whole thing has indeed nothing to do with either perfection nor encryption. === Subject: Re: How much lossless compression is possible in images? > So perfectly compressed messages are perfectly encrypted? It is possible to devise an algorithm that will compress any specific message to a single bit. If the entropy of the portion of the algorithm held confidential is at least equal to the length of the original message, this constitutes unbreakable encryption. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? ... >> def compress(I): >> if I == I_0: >> return a single 0 byte >> else: >> return a 1, followed by I. >> >> I leave the decompressor as an exercise. ... > def decompress(data): > if data == '0': > return I_0 > else: > return data with first byte omitted ... > You are not trying seriously Ullrich. You have not even started to > define what you mean by compressing. If you care to check the > literature, you will find that compression is said to have taken place > when the representation of both the decompressing algorithm and the > output are of lesser total length than the input. And if *you* care to check the literature you will find that a compression algorithm is an algorithm that compresses a particular kind of input. David's algorithm satisfies that definition. > Apart from that, your construction fails for the input '0' since it > does not compress it under any definition of compression you might wish > to choose, therefore your statement is wrong in any case. So? That input is not in the class of inputs for which the compressor is intended. By your definition compressors and compression algorithms do not exist. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > ... > >> def compress(I): > >> if I == I_0: > >> return a single 0 byte > >> else: > >> return a 1, followed by I. > >> > >> I leave the decompressor as an exercise. > ... > > def decompress(data): > > if data == '0': > > return I_0 > > else: > > return data with first byte omitted > ... > > You are not trying seriously Ullrich. You have not even started to > > define what you mean by compressing. If you care to check the > > literature, you will find that compression is said to have taken place > > when the representation of both the decompressing algorithm and the > > output are of lesser total length than the input. > And if *you* care to check the literature you will find that a compression > algorithm is an algorithm that compresses a particular kind of input. > David's algorithm satisfies that definition. Well said Winter however absurdly tautologic it is. An algorithm which does not compress any kind of input wouldn't be a compressor would it? And an algorithm which compresses any kind of input does not exist, believing in such would rather put you on the wacky side of crankdom. So there should be no doubt that we agree here, however, pray tell me how does your statement affect my objection to Ullrich's construction? > > Apart from that, your construction fails for the input '0' since it > > does not compress it under any definition of compression you might wish > > to choose, therefore your statement is wrong in any case. > So? That input is not in the class of inputs for which the compressor > is intended. By your definition compressors and compression > algorithms do not exist. Sorry Winter you seem to have lost the thread of our little discussion here. Ullrich stated that There's no such thing as an incompressible image, _until_ you specify what algorithm you're using. Given _any_ Image I_0 there _is_ a lossless compression algorithm that compresses I_0 to a one-byte file and then procedes to show how to construct such an algorithm. Note how he uses the word any and makes it clear that he is not excluding any inputs at all, as opposed to what you are now saying. His statement is wrong, because for the Input '0' his construction of a compressing algorithm fails. Well it's really trivial, but this is sci.math after all, isn't it? > dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 > home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? >> ... >> >> def compress(I): >> >> if I == I_0: >> >> return a single 0 byte >> >> else: >> >> return a 1, followed by I. >> >> >> >> I leave the decompressor as an exercise. >> ... >> > def decompress(data): >> > if data == '0': >> > return I_0 >> > else: >> > return data with first byte omitted >> ... >> > You are not trying seriously Ullrich. You have not even started to >> > define what you mean by compressing. If you care to check the >> > literature, you will find that compression is said to have taken >place >> > when the representation of both the decompressing algorithm and >the >> > output are of lesser total length than the input. >> And if *you* care to check the literature you will find that a >compression >> algorithm is an algorithm that compresses a particular kind of input. >> David's algorithm satisfies that definition. >Well said Winter however absurdly tautologic it is. An algorithm which >does not compress any kind of input wouldn't be a compressor would it? >And an algorithm which compresses any kind of input does not exist, >believing in such would rather put you on the wacky side of crankdom. >So there should be no doubt that we agree here, however, pray tell me >how does your statement affect my objection to Ullrich's construction? >> > Apart from that, your construction fails for the input '0' since >> > does not compress it under any definition of compression you might >wish >> > to choose, therefore your statement is wrong in any case. >> So? That input is not in the class of inputs for which the >compressor >> is intended. By your definition compressors and compression >> algorithms do not exist. >Sorry Winter you seem to have lost the thread of our little discussion >here. Ullrich stated that There's no such thing as an incompressible >image, _until_ you specify what algorithm you're using. Given _any_ >Image I_0 there _is_ a lossless compression algorithm that compresses >I_0 to a one-byte file and then procedes to show how to construct such >an algorithm. Note how he uses the word any and makes it clear that >he is not excluding any inputs at all, as opposed to what you are now >saying. His statement is wrong, because for the Input '0' his >construction of a compressing algorithm fails. Well it's really >trivial, but this is sci.math after all, isn't it? Uh, yes, it's sci.math. Hence we should be able to tell the difference between There exists an algorithm which will compress any input (um, the English is actually ambiguous here, what we mean is There exists an algorithm A such that for every input I, A compresses I.) and Given an input, there exists an algorithm which will compress it. The first is easily seen to be false by a counting argument, while the second is true, as I've shown. The _point_ to the second is exactly as I said: People shouldn't talk about incompressible input as though this had some absolute meaning - it doesn't. It doesn't mean anything _until_ we have specified what algorithm we're using. (heh-heh: On a related topic, for years I saw people around here discuss Kolomogorov complexity without reference to a programming language, as though length of the smallest algorithm implementing a function had some absolute meaning. Was a great relief one day when I looked at something Chaitin had written and saw that he _began_ by saying that of course we need to first specify a programming language before any of these concepts make sense...) >> dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, >+31205924131 >> home: bovenover 215, 1025 jn amsterdam, nederland; >http://www.cwi.nl/~dik/ ************************ David C. Ullrich === Subject: Re: How much lossless compression is possible in images? >> ... >> >> def compress(I): >> >> if I == I_0: >> >> return a single 0 byte >> >> else: >> >> return a 1, followed by I. >> >> >> >> I leave the decompressor as an exercise. >> ... >> > def decompress(data): >> > if data == '0': >> > return I_0 >> > else: >> > return data with first byte omitted >> ... >> > You are not trying seriously Ullrich. You have not even started to >> > define what you mean by compressing. If you care to check the >> > literature, you will find that compression is said to have taken >place >> > when the representation of both the decompressing algorithm and >the >> > output are of lesser total length than the input. >> >> And if *you* care to check the literature you will find that a >compression >> algorithm is an algorithm that compresses a particular kind of input. >> David's algorithm satisfies that definition. >Well said Winter however absurdly tautologic it is. An algorithm which >does not compress any kind of input wouldn't be a compressor would it? >And an algorithm which compresses any kind of input does not exist, >believing in such would rather put you on the wacky side of crankdom. >So there should be no doubt that we agree here, however, pray tell me >how does your statement affect my objection to Ullrich's construction? >> > Apart from that, your construction fails for the input '0' since >it >> > does not compress it under any definition of compression you might >wish >> > to choose, therefore your statement is wrong in any case. >> >> So? That input is not in the class of inputs for which the >compressor >> is intended. By your definition compressors and compression >> algorithms do not exist. >Sorry Winter you seem to have lost the thread of our little discussion >here. Ullrich stated that There's no such thing as an incompressible >image, _until_ you specify what algorithm you're using. Given _any_ >Image I_0 there _is_ a lossless compression algorithm that compresses >I_0 to a one-byte file and then procedes to show how to construct such >an algorithm. Note how he uses the word any and makes it clear that >he is not excluding any inputs at all, as opposed to what you are now >saying. His statement is wrong, because for the Input '0' his >construction of a compressing algorithm fails. Well it's really >trivial, but this is sci.math after all, isn't it? > Uh, yes, it's sci.math. Hence we should be able to tell the > difference between > There exists an algorithm which will compress any input > (um, the English is actually ambiguous here, what we mean > is There exists an algorithm A such that for every input I, > A compresses I.) > and > Given an input, there exists an algorithm which will > compress it. > The first is easily seen to be false by a counting argument, > while the second is true, as I've shown. You have shown nothing until you tell us what you mean by will compress it > The _point_ to the second is exactly as I said: People > shouldn't talk about incompressible input as though this > had some absolute meaning - it doesn't. It doesn't mean > anything _until_ we have specified what algorithm we're > using. Wrong Ullrich, people shouldn't talk about anything at all, unless they have anything truly interesting to say. Want to know something Ullrich? Although I've been acting the role of a prick as far as you might be concerned, I'm quite interested in what you may have to say regarding compression (providing you bother to take a bit of a deeper look at it). > (heh-heh: On a related topic, for years I saw people > around here discuss Kolomogorov complexity without > reference to a programming language, as though length > of the smallest algorithm implementing a function had > some absolute meaning. Was a great relief one day when > I looked at something Chaitin had written and saw > that he _began_ by saying that of course we need to > first specify a programming language before any of > these concepts make sense...) Exactly Ullrich, just as your just said. >> dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, >+31205924131 >> home: bovenover 215, 1025 jn amsterdam, nederland; >http://www.cwi.nl/~dik/ > ************************ > David C. Ullrich === Subject: Re: How much lossless compression is possible in images? >> ... >> >> def compress(I): >> >> if I == I_0: >> >> return a single 0 byte >> >> else: >> >> return a 1, followed by I. >> >> >> >> I leave the decompressor as an exercise. >> ... >> > def decompress(data): >> > if data == '0': >> > return I_0 >> > else: >> > return data with first byte omitted >> ... >> > You are not trying seriously Ullrich. You have not even started to >> > define what you mean by compressing. If you care to check the >> > literature, you will find that compression is said to have taken >place >> > when the representation of both the decompressing algorithm and >the >> > output are of lesser total length than the input. >> >> And if *you* care to check the literature you will find that a >compression >> algorithm is an algorithm that compresses a particular kind of input. >> David's algorithm satisfies that definition. >Well said Winter however absurdly tautologic it is. An algorithm which >does not compress any kind of input wouldn't be a compressor would it? >And an algorithm which compresses any kind of input does not exist, >believing in such would rather put you on the wacky side of crankdom. >So there should be no doubt that we agree here, however, pray tell me >how does your statement affect my objection to Ullrich's construction? >> > Apart from that, your construction fails for the input '0' since >it >> > does not compress it under any definition of compression you might >wish >> > to choose, therefore your statement is wrong in any case. >> >> So? That input is not in the class of inputs for which the >compressor >> is intended. By your definition compressors and compression >> algorithms do not exist. >Sorry Winter you seem to have lost the thread of our little discussion >here. Ullrich stated that There's no such thing as an incompressible >image, _until_ you specify what algorithm you're using. Given _any_ >Image I_0 there _is_ a lossless compression algorithm that compresses >I_0 to a one-byte file and then procedes to show how to construct such >an algorithm. Note how he uses the word any and makes it clear that >he is not excluding any inputs at all, as opposed to what you are now >saying. His statement is wrong, because for the Input '0' his >construction of a compressing algorithm fails. Well it's really >trivial, but this is sci.math after all, isn't it? > Uh, yes, it's sci.math. Hence we should be able to tell the > difference between > There exists an algorithm which will compress any input > (um, the English is actually ambiguous here, what we mean > is There exists an algorithm A such that for every input I, > A compresses I.) > and > Given an input, there exists an algorithm which will > compress it. > The first is easily seen to be false by a counting argument, > while the second is true, as I've shown. You have shown nothing until you tell us what you mean by will compress it > The _point_ to the second is exactly as I said: People > shouldn't talk about incompressible input as though this > had some absolute meaning - it doesn't. It doesn't mean > anything _until_ we have specified what algorithm we're > using. Wrong Ullrich, people shouldn't talk about anything at all, unless they have anything truly interesting to say. Want to know something Ullrich? Although I've been acting the role of a prick as far as you might be concerned, I'm quite interested in what you may have to say regarding compression (providing you bother to take a bit of a deeper look at it). > (heh-heh: On a related topic, for years I saw people > around here discuss Kolomogorov complexity without > reference to a programming language, as though length > of the smallest algorithm implementing a function had > some absolute meaning. Was a great relief one day when > I looked at something Chaitin had written and saw > that he _began_ by saying that of course we need to > first specify a programming language before any of > these concepts make sense...) Exactly Ullrich, just as your just said. >> dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, >+31205924131 >> home: bovenover 215, 1025 jn amsterdam, nederland; >http://www.cwi.nl/~dik/ > ************************ > David C. Ullrich === Subject: Re: How much lossless compression is possible in images? >> Assuming ideal compression that removes every trace of redundancy from >> an image, how much lossless compression might really be possible? I >> know this is a difficult question because so much depends on image >> content, but I'm just trying to get an idea of how close current >> lossless compression methods are to the ideal. Visually images seem to >> be very highly redundant, although current lossless algorithms only >> manage about 50% compression. But assuming time and space were not >> constraints, how far could one theoretically go? >> >> -- >> Transpose hotmail and mxsmanic in my e-mail address to reach me > directly. >> It depends totally on image content. >> An image consisting of random pixels will not compress at all (0% >> compression) using a generic algorithm; an image consisting of entirely > one >> colour will compress almost to zero (almost 100% compression). > I don't have the math at hand, but I believe that a truly random image > would have at least some compressible areas. In a strange sense, a > completely incompressible image would be as ordered as a single color > image. Well, you would be wrong. At least one definition of random is that an image can't be compressed. I know of no definition of random which would allow every or even most random images to have at least some compressible areas. And what is completely incompressible image supposed to mean? Here's a little mathematical titbit, which follows immediately from the pigeon hole principle: The average image size (averaged across all possible images) of images compressed using lossless algorithms must be equal to or greater than the uncompressed image size. Indeed, for all practical lossless compression algorithms, the huge majority of all all images are larger when compressed than they are before compression. Its just the tiny minority of images which get smaller are those that have characteristics often found in photos - such as large areas with only moderate colour variability. === Subject: Re: How much lossless compression is possible in images? > Well, you would be wrong. At least one definition of random is that an > image can't be compressed. More precisely perhaps, the average compression possible for random images approaches zero as the number of images approaches infinity. However, since a given random image may (unpredictably) contain any degree of redundancy, virtually all random images are compressible to some extent using some algorithms. Put still another way, no algorithm exists (or can be devised) that will compress a random string of bits more than 50% of the time. In fact, no matter what the algorithm is, it will produce a shorter output string 50% of the time, and a longer output string the other 50% of the time. > I know of no definition of random which would > allow every or even most random images to have at least some compressible > areas. See above. > The average image size (averaged across all possible images) of images > compressed using lossless algorithms must be equal to or greater than the > uncompressed image size. Yes. Compression algorithms work only because all possible images are not equally probable. For every possible image that can be compressed, there exists some other image that will increase in size by the same amount after compression, if the compression is lossless (reversible). In real life, image data corresponding to pictorial representations is far more probable than random image data (even though the number of non-pictoral images possible vastly exceeds the number of pictoral images possible). So compression works. > Indeed, for all practical lossless compression algorithms, the huge majority > of all all images are larger when compressed than they are before > compression. Its just the tiny minority of images which get smaller are > those that have characteristics often found in photos - such as large areas > with only moderate colour variability. Yes. A different way of stating what I've said above. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? ... > Put still another way, no algorithm exists (or can be devised) that will > compress a random string of bits more than 50% of the time. Even 50% cannot be reached. > In fact, no > matter what the algorithm is, it will produce a shorter output string > 50% of the time, and a longer output string the other 50% of the time. Wrong. It will produce a shorter string less than 50% of the time, and it will produce an equal sized or longer string in the remaining cases. See David Ullrich's excellent algorithm that reduces exactly one bitstring in size and increases the size of all others. As another example, take the algorithm that leaves strings starting with (binary) 1 alone, that encodes a particular string that starts with 00 as plain 00, and prepends 01 to all other strings starting with 0. One string is shortened, 50 % stays equal in size and the remainder is lengthened. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > Even 50% cannot be reached. True, but it can be very closely approached. The longer the message, the closer the approach, but as long as the message is of finite length, it will never be 50% exactly. > Wrong. It will produce a shorter string less than 50% of the time, and it > will produce an equal sized or longer string in the remaining cases. I left out the details, but I suspected someone would grab the opportunity to show how much more he knew, thus saving me some bandwidth. > See > David Ullrich's excellent algorithm that reduces exactly one bitstring > in size and increases the size of all others. Average the changes in size, and you'll find that the total reduction in size for the one string equals the total increase for all other strings. This is at least the theoretical case. It's easy to cheat with a real algorithm, though. > As another example, take > the algorithm that leaves strings starting with (binary) 1 alone, that > encodes a particular string that starts with 00 as plain 00, and prepends > 01 to all other strings starting with 0. One string is shortened, 50 % > stays equal in size and the remainder is lengthened. See above. The total change in length will converge on zero. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? ... > See > David Ullrich's excellent algorithm that reduces exactly one bitstring > in size and increases the size of all others. > Average the changes in size, and you'll find that the total reduction in > size for the one string equals the total increase for all other strings. Do you think so? One bitstring is reduced in size to 1 bit, and all other bitstrings increase by 1 bit. > This is at least the theoretical case. It's easy to cheat with a real > algorithm, though. What do you mean by theoretical and real here? And what do you mean with cheating? > As another example, take > the algorithm that leaves strings starting with (binary) 1 alone, that > encodes a particular string that starts with 00 as plain 00, and prepends > 01 to all other strings starting with 0. One string is shortened, 50 % > stays equal in size and the remainder is lengthened. > See above. The total change in length will converge on zero. In what sense? Suppose the particular string is 'k' bits. It will be reduced by 'k-1' bits. All other strings that start with 0 are lengthened by 2 bits. There are 2^(m-1) such strings of size m. So when we consider the total change in length it is '2^m - k + 1'. I do not see any sense in which this converges to zero. Even if we divide by the number of strings considered ('2^m') and take the average, it will converge to 1, not 0. So in the limit this algorithm will increase the size on average by 1 bit. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > Do you think so? Yes. > One bitstring is reduced in size to 1 bit, and all other > bitstrings increase by 1 bit. Yes. So one string is reduced by 1,000,000 bits, and a million other strings increase by 1 bit. The net change is zero. > What do you mean by theoretical and real here? The perfect algorithms of theory, versus real algorithms that need not follow all aspects of theory. > In what sense? Suppose the particular string is 'k' bits. It will be > reduced by 'k-1' bits. All other strings that start with 0 are lengthened > by 2 bits. There are 2^(m-1) such strings of size m. So when we consider the > total change in length it is '2^m - k + 1'. I do not see any sense > in which this converges to zero. Even if we divide by the number of > strings considered ('2^m') and take the average, it will converge to 1, > not 0. So in the limit this algorithm will increase the size on average > by 1 bit. In the real world, I'll concede that it would not converge on exactly zero. A compression algorithm is an algorithm that converts fixed-length bit strings of unequal probabilities to variable-length bit strings such that the most probable input strings have the shortest output strings. The total number of information bits for all output messages cannot be less than the total number of information bits for all input messages, but offhand I don't see why it must be greater, at least in theory. In the real-world, algorithms always add a few bits to the total on output. output strings (is it part of the output information or not?). -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > Do you think so? > Yes. > One bitstring is reduced in size to 1 bit, and all other > bitstrings increase by 1 bit. > Yes. So one string is reduced by 1,000,000 bits, and a million other > strings increase by 1 bit. The net change is zero. > What do you mean by theoretical and real here? > The perfect algorithms of theory, versus real algorithms that need not > follow all aspects of theory. > In what sense? Suppose the particular string is 'k' bits. It will be > reduced by 'k-1' bits. All other strings that start with 0 are lengthened > by 2 bits. There are 2^(m-1) such strings of size m. So when we consider the > total change in length it is '2^m - k + 1'. I do not see any sense > in which this converges to zero. Even if we divide by the number of > strings considered ('2^m') and take the average, it will converge to 1, > not 0. So in the limit this algorithm will increase the size on average > by 1 bit. > In the real world, I'll concede that it would not converge on exactly > zero. > A compression algorithm is an algorithm that converts fixed-length bit > strings of unequal probabilities to variable-length bit strings such > that the most probable input strings have the shortest output strings. > The total number of information bits for all output messages cannot be > less than the total number of information bits for all input messages, > but offhand I don't see why it must be greater, at least in theory. In > the real-world, algorithms always add a few bits to the total on output. > output strings (is it part of the output information or not?). > -- > Transpose hotmail and mxsmanic in my e-mail address to reach me directly. Here is some advice for you lout. Read about Kraft's inequality. Read the comp compression faq. Ask pertinent questions in that forum. After you're done, it will still be your choice to make an ass of yourself === Subject: Re: How much lossless compression is possible in images? > Do you think so? > Yes. > One bitstring is reduced in size to 1 bit, and all other > bitstrings increase by 1 bit. > Yes. So one string is reduced by 1,000,000 bits, and a million other > strings increase by 1 bit. The net change is zero. > What do you mean by theoretical and real here? > The perfect algorithms of theory, versus real algorithms that need not > follow all aspects of theory. > In what sense? Suppose the particular string is 'k' bits. It will be > reduced by 'k-1' bits. All other strings that start with 0 are lengthened > by 2 bits. There are 2^(m-1) such strings of size m. So when we consider the > total change in length it is '2^m - k + 1'. I do not see any sense > in which this converges to zero. Even if we divide by the number of > strings considered ('2^m') and take the average, it will converge to 1, > not 0. So in the limit this algorithm will increase the size on average > by 1 bit. > In the real world, I'll concede that it would not converge on exactly > zero. > A compression algorithm is an algorithm that converts fixed-length bit > strings of unequal probabilities to variable-length bit strings such > that the most probable input strings have the shortest output strings. > The total number of information bits for all output messages cannot be > less than the total number of information bits for all input messages, > but offhand I don't see why it must be greater, at least in theory. In > the real-world, algorithms always add a few bits to the total on output. > output strings (is it part of the output information or not?). > -- > Transpose hotmail and mxsmanic in my e-mail address to reach me directly. Here is some advice for you lout. Read about Kraft's inequality. Read the comp compression faq. Ask pertinent questions in that forum. After you're done, it will still be your choice to make an ass of yourself === Subject: Re: How much lossless compression is possible in images? > Here is some advice for you lout. Read about Kraft's inequality. Read > the comp compression faq. Ask pertinent questions in that forum. > After you're done, it will still be your choice to make an ass of > yourself Why do you seem to limit your posts to others to personal attacks? -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <5skfr0pb3p24nn2lthl7amb9eai1bf9rtr@4ax.com> > Here is some advice for you lout. Read about Kraft's inequality. Read > the comp compression faq. Ask pertinent questions in that forum. > After you're done, it will still be your choice to make an ass of > yourself > Why do you seem to limit your posts to others to personal attacks? Do not be unfair even if you do not like the way I talk to you. It seems to me that I am the only one to have actually attempted to answer your original question. Appart from that, I have tried to stop even more noise from entering this discussion. Noise which among others you keep introducing by constantly stating totally baseless bull. You might notice that others have tried to tell you the same thing in a much more civil manner than I, but you simply keep ignoring them. > -- > Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? > Here is some advice for you lout. Here some advice for you. Do not post things multiple times, how easy help. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > > Here is some advice for you lout. > Here some advice for you. Do not post things multiple times, how easy also > help. it seems to be happening quite a lot since they introduced the beta of the new version. Some posts seem to get lost too. It is not my intention to flood. As for the nasty style, well you can't please everybody all of the time, Winter. I'm sorry for any distress it may cause to you personally, since you are not among those I dislike or intend to be uncivil to. I find empty minded prattling of the kind the OP can't seem to quit posting, as annoying as others find my style. === Subject: Re: How much lossless compression is possible in images? ... > One bitstring is reduced in size to 1 bit, and all other > bitstrings increase by 1 bit. > Yes. So one string is reduced by 1,000,000 bits, and a million other > strings increase by 1 bit. The net change is zero. Or one string is reduced by 1,000 bits and a million other strings increasy by 1 bit. The net change is non-zero. You are assuming, without reason, that all strings are equally long. > What do you mean by theoretical and real here? > The perfect algorithms of theory, versus real algorithms that need not > follow all aspects of theory. What is a perfect algorithm of theory? I have honestly no idea. > In what sense? Suppose the particular string is 'k' bits. It will be > reduced by 'k-1' bits. All other strings that start with 0 are lengthened > by 2 bits. There are 2^(m-1) such strings of size m. So when we consider Sorry I meant here, there are 2^m - 1 such string of size <= m (m >= k). > the total change in length it is '2^m - k + 1'. I do not see any sense And this changes to '2^(m+1) - k + 1'. Other changes apply. > in which this converges to zero. Even if we divide by the number of > strings considered ('2^m') and take the average, it will converge to 1, > not 0. So in the limit this algorithm will increase the size on average > by 1 bit. > In the real world, I'll concede that it would not converge on exactly > zero. With the modification above it would not converge even to a number close to 1. It will diverge. > A compression algorithm is an algorithm that converts fixed-length bit > strings of unequal probabilities to variable-length bit strings such > that the most probable input strings have the shortest output strings. Why fixed-length bit strings? Almost all compression algorithms work on variable length input, not on fixed length input. And when you consider probabilities, the optimal algorithm for the input can be expected to *decrease* the size in general. > The total number of information bits for all output messages cannot be > less than the total number of information bits for all input messages, > but offhand I don't see why it must be greater, at least in theory. That entirely depends on the algorithm. With most compression algorithms the number of information bits for all input messages will *increase* because the compression algorithm has in most cases to store some additional information in the output stream to let the decompressor work. Consider the easiest scheme of all: huffman encoding. If the input is not totally random, the size of the message will become shorter, but the coding table has also to be included in the output, which may make some of the output strings longer. In addition there are the totally random strings that inherently grow longer by the addition of the coding table. I cannot see why it must be smaller or equal, because you are adding in additional information. Now if your compression uses a fixed coding table things might be different. Off-hand I do not know, but I expect that in that case indeed total sizes might be equal. > but offhand I don't see why it must be greater, at least in theory. In > the real-world, algorithms always add a few bits to the total on output. > output strings (is it part of the output information or not?). Yes, of course. It is necessary to make the decompressor work. Consider run-length encoding on bytes. You need a marker to show that the next byte is a count and not a plain byte. On the other hand, when the next plain byte is the marker you have to do other things (that increase the code) to let that show. So suppose you use 255 as marker, the next byte when it has the value 0..254 as a count of 4..258, and a plain byte of 255 just be doubled. Now you know that all strings that do not contain the 255 byte will decrease in size or stay equal. All strings that contain the 255 byte and do not contain a repetition of 4 or more equal bytes will increase in size. For the remainder it can go either way. I *think* that in the end the total size of all possible messages will be larger. On the other hand, the additional information put in the stream by the compressor is needed for decompression. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: How much lossless compression is possible in images? > What is a perfect algorithm of theory? I have honestly no idea. To me, it's an algorithm that accomplishes its compression without any overhead. > Why fixed-length bit strings? For simplicity. > Now if your compression uses a fixed coding table things > might be different. Off-hand I do not know, but I expect that in that > case indeed total sizes might be equal. In theory a compression algorithm just performs a simple substitution. It should not have to produce a total number of output bits for all possible strings that is greater than the total number of input bits for all possible strings. But I haven't considered this in depth and I may be missing something. This would have to be a perfect algorithm, as well, that is, one that adds no overhead. > Yes, of course. It is necessary to make the decompressor work. Consider > run-length encoding on bytes. You need a marker to show that the next > byte is a count and not a plain byte. On the other hand, when the next > plain byte is the marker you have to do other things (that increase the > code) to let that show. So suppose you use 255 as marker, the next > byte when it has the value 0..254 as a count of 4..258, and a plain byte > of 255 just be doubled. Now you know that all strings that do not > contain the 255 byte will decrease in size or stay equal. All strings > that contain the 255 byte and do not contain a repetition of 4 or more > equal bytes will increase in size. For the remainder it can go either way. > I *think* that in the end the total size of all possible messages will be > larger. The question is, does there exist an algorithm that does not add any overhead? I think a simple substitution table would qualify, but I'm not sure, nor am I sure how the length of strings is to be treated (is it counted as part of the encoded information in the string?). -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <41b4079b$0$20858$afc38c87@news.optusnet.com.au> bla bla > Put still another way, no algorithm exists (or can be devised) that will > compress a random string of bits more than 50% of the time. In fact, no > matter what the algorithm is, it will produce a shorter output string > 50% of the time, and a longer output string the other 50% of the time. You started asking a question, now you are making wild assertions. Where is the math to prove the above bull? > Yes. Compression algorithms work only because all possible images are > not equally probable. Oh so there are actually images that are more probable than others? Give an example. If an image can be represented by a binary string of length n then there are 2^n such possible images. Each one of them is equally probable. Most compression algorithms work by ASSUMING that some images are more probable than others and assign them shorter representations, thus compressing those images which are more probable under the assumed restrictions. [snip more absurd prattling] === Subject: Re: How much lossless compression is possible in images? > You started asking a question, now you are making wild assertions. There's nothing wild about the assertion. > Where is the math to prove the above bull? Shannon provided most of it. I'm not a mathematician. However, I do understand the concepts, which are practically self-evident. > Oh so there are actually images that are more probable than others? In real-world image processing, yes, very much so. The set of all possible images of n bits in size contains 2^n images, which is extraordinarily large for the types of images being manipulated today (the image on the monitor of my PC, for example, is only one of 10^13871462 possible images that can be displayed). Only a very, very small fraction of these are useful pictorial images--most are random pixels. (It is sometimes interesting to consider exactly which images are contained in these sets.) Anyway, all image compression algorithms correctly assume that certain subsets of all possible images are vastly more probable than all other images. These probable images share a lot of common characteristics, such as very high redundancy, that can be exploited by the algorithms to produce significant compression for the targeted subset of images. These same algorithms will produce marginally _larger_ output files for the much more random images that they are unlikely to ever be called upon to compress (the increase in size would be very small, though, since there are so many such images). All of this is basic information theory (basic because even I understand it). > Give an example. See above. > If an image can be represented by a binary string of > length n then there are 2^n such possible images. Each one of them is > equally probable. Not in the real world. Only certain images are probable in the real world of pictorial image processing. All image compression algorithms are designed to provide high compression for this subset of highly probable images, at the expense of negative compression for all other possible images (which vastly outnumber the pictorial images but are extremely improbable). > Most compression algorithms work by ASSUMING that > some images are more probable than others and assign them shorter > representations, thus compressing those images which are more probable > under the assumed restrictions. Yes. The assumption is correct, which is why compression algorithms work. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <41b4079b$0$20858$afc38c87@news.optusnet.com.au> > You started asking a question, now you are making wild assertions. > There's nothing wild about the assertion. > Where is the math to prove the above bull? > Shannon provided most of it. I'm not a mathematician. However, I do > understand the concepts, which are practically self-evident. Now now,you snipped the statement that is being argued. Are you being plain unpolite here or are you being falacious ? You stated (i quote) In fact,no matter what the algorithm is, it will produce a shorter output string 50% of the time, and a longer output string the other 50% of the time. This is wildly asserted bull, Shannons paper is available for download, please indicate where he proved that nonsense. > Oh so there are actually images that are more probable than others? > In real-world image processing, yes, very much so. The set of all Exactly. Under the assumpition of restrictions i.e. real-world image processing (I'm willing to suppose that you mean something like the kind of images we are interested in dealing with) certain images are more probable. Without restrictions no image is more probable than any other. The distinction is crucial in getting an answer to your original question. Which is that basically, the limit of compressibility of an image depends on the model (the set of conditions that are being assumed), so that your question cannot be satisfactorily be answered. However, once you establish a model you can measure the entropy of any image (under that model) which is an exact measure of the compressibility. > All of this is basic information theory (basic because even I > understand it). It seems that you got most of it right but you need to work on it a bit more. > Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? Originator: richard@cogsci.ed.ac.uk (Richard Tobin) >> I don't have the math at hand, but I believe that a truly random image >> would have at least some compressible areas. >Well, you would be wrong. At least one definition of random is that an >image can't be compressed. I know of no definition of random which would >allow every or even most random images to have at least some compressible >areas. Suppose you choose some compression algorithm - simple run-length encoding of bytes for example. Suppose it uses a byte for the length. Any sequence of 3 or more equal bytes will be compressible. Any reasonably large image will have such a sequence in it, so it will have a part that can be compressed. (A large image that didn't have such a sequence would be most unlikely, if it really was random.) So it's true that sufficiently large random images will have some compressible areas. This doesn't do you any good in practice, because you need to distinguish the compressed areas from non-compressed areas that just happen to have the same values. You need extra bits for this, so you won't end up with any compression overall. >The average image size (averaged across all possible images) of images >compressed using lossless algorithms must be equal to or greater than the >uncompressed image size. The unix compress program always produces a file which is the same size as the original or smaller, which it achieves by not compressing the file if compression would not make it smaller. However, it appends .Z to the filename if it compresses it, and you have to take those extra bytes into acccount when determining the real compression ratio. -- Richard === Subject: Re: How much lossless compression is possible in images? >> >> Assuming ideal compression that removes every trace of redundancy from >> an image, how much lossless compression might really be possible? I >> know this is a difficult question because so much depends on image >> content, but I'm just trying to get an idea of how close current >> lossless compression methods are to the ideal. Visually images seem to >> be very highly redundant, although current lossless algorithms only >> manage about 50% compression. But assuming time and space were not >> constraints, how far could one theoretically go? >> >> -- >> Transpose hotmail and mxsmanic in my e-mail address to reach me > directly. >> >> It depends totally on image content. >> >> An image consisting of random pixels will not compress at all (0% >> compression) using a generic algorithm; an image consisting of entirely > one >> colour will compress almost to zero (almost 100% compression). > I don't have the math at hand, but I believe that a truly random image > would have at least some compressible areas. In a strange sense, a > completely incompressible image would be as ordered as a single color > image. > Well, you would be wrong. At least one definition of random is that an > image can't be compressed. I know of no definition of random which would > allow every or even most random images to have at least some compressible > areas. > And what is completely incompressible image supposed to mean? How about an image consisting of random pixels [that] will not compress at all? === Subject: Re: How much lossless compression is possible in images? > >> >> Assuming ideal compression that removes every trace of redundancy > from >> an image, how much lossless compression might really be possible? I >> know this is a difficult question because so much depends on image >> content, but I'm just trying to get an idea of how close current >> lossless compression methods are to the ideal. Visually images seem > to >> be very highly redundant, although current lossless algorithms only >> manage about 50% compression. But assuming time and space were not >> constraints, how far could one theoretically go? >> >> -- >> Transpose hotmail and mxsmanic in my e-mail address to reach me > directly. >> >> It depends totally on image content. >> >> An image consisting of random pixels will not compress at all (0% >> compression) using a generic algorithm; an image consisting of entirely > one >> colour will compress almost to zero (almost 100% compression). > > I don't have the math at hand, but I believe that a truly random image > would have at least some compressible areas. In a strange sense, a > completely incompressible image would be as ordered as a single color > image. > > > Well, you would be wrong. At least one definition of random is that an > image can't be compressed. I know of no definition of random which would > allow every or even most random images to have at least some compressible > areas. > And what is completely incompressible image supposed to mean? > How about an image consisting of random pixels [that] will not compress at > all? What about the old pigeonhole principle: Any lossless encoding scheme that compresses at least one image will increase the size of some other image. === Subject: Re: How much lossless compression is possible in images? > How about an image consisting of random pixels [that] will not compress at > all? It is always possible to devise an algorithm that will compress any one given image, no matter how random it may appear to be. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <41b4079b$0$20858$afc38c87@news.optusnet.com.au> >It is always possible to devise an algorithm that will compress any one >given image, no matter how random it may appear to be. that in itself sounds like an algorithm, so you may find the algorithm you find is bigger than the image. Herc === Subject: Re: How much lossless compression is possible in images? > that in itself sounds like an algorithm, so you may find the algorithm > you find is bigger than the image. Not if it is designed only to compress one specific image. A generalized algorithm to generate such an algorithm for any arbitrary image would indeed be unwieldy, although I'm too lazy to try to figure out a lower bound for its size. -- Transpose hotmail and mxsmanic in my e-mail address to reach me directly. === Subject: Re: How much lossless compression is possible in images? <41b3ed05$0$9113$afc38c87@news.optusnet.com.au> <41b4079b$0$20858$afc38c87@news.optusnet.com.au> The point here is any compression algorithm, or system of compression algorithms, operating on the total set of inputs, cannot get a total compression over the entire set. Consider 2MB 1000 pixels X 1000 pixels Raw Data Compressed File 1 66 2 44 3 2 4 1 5 .. .. 16^1,000,000 There are 16^1,000,000 possible picture files, so there must be 16^1,000,000 distinct compressed files. You can't have 16^1,000,000 distinct files unless the average file length is over 1MB. The average file length of the original 16^1,000,000 images is also 1MB. Therefore, not every picture gets compressed. Finding a particular compression algorithm for that image doesn't help in the global scheme of things, because you have to say what the algorithm is, and it wont be small. The length of the algorithm + the compressed file will tend to be larger than the original file. The exceptions are easily compressible data, lots of flat areas. Herc === Subject: Questions of Higher Order Derivatives; and their Inverses Can someone provide me with a better proof than this; somehow I missed this relation in undergraduate calculus: (d^2s/dt^2)(dt/ds)^3 = -d^2t/ds^2 I differentiate the unit tangent vector, T =dr/ds, with respect to t: dT/dt = d(dr/ds)/dt = d(dr/dt)(dt/ds)/dt = (d^2r/dt^2)(dt/ds) + (d^2t/ds^2)(ds/dt)(dr/dt) = (d^2r/ds^2)(ds/dt) multiply by (dt/ds): (dT/dt)(dt/ds) = d^2r/ds^2 = (d^2r/dt^2)(dt/ds)^2 + (d^2t/ds^2)(dr/dt) (A) In literature, in matrix form (stated without proof, easy enough to do), I find: | (ds/dt) (d^2s/dt^2)| d^2r/ds^2 = | | * (dt/ds)^3 | (dr/dt) (d^r/dt^2)| or, = (d^2r/dt^2)(dt/ds)^2 - (dr/dt)(d^2s/dt^2)(dt/ds)^3 (B) if Equation (A) = Equation (B) then, (d^2s/dt^2)(dt/ds)^3 = -(d^2t/ds^2) I extend it this way: (ds/dt)(dt/ds)^2 = dt/ds (d^2s/dt^2)(dt/ds)^3 = -d^2t/ds^2 (d^3s/dt^3)(dt/ds)^4 = d^3t/ds^3 (d^4s/dt^4)(dt/ds)^5 = -d^4t/ds^4 I also have a similar proof for: (d^2r/dt^2)(dt/ds)^2 = (d^2r/ds^2) But have not known of these simple relations; nor have been able to make a simple proof of it, using the definition of differentiation or at least using: Du^n/dx = [(1/n)u ^(n-1)]dx I really don't have the necessary understanding of differentials, and differentiation, to prove the relations directly, or to even ask the proper questions, I guess; can someone help? Charles === Subject: Re: topology 22 >>find the subset W,X,Y,Z of real topology R >>which satisfy (1),(2),(3),(4). >>(without proof) >> >>(1) Y,Z is connected set >>(2) Y in W in Z , Y in X in Z > I don't get this, how can a subset of R can be in a subset of R? > The elements of a subset of R are numbers, aren't subsets of R. > This is a problem of the imprecise use of the word in. Sloppy and confusing. > A person might say the number 1 is in the interval [0, 2], > and the same person might say the subset [1,2] is in the > same interval. The OP should probably have used a different > set of words. How weird. Does 'in' mean 'subset'? That doesn't make sense. === Subject: Re: topology 22 >>find the subset W,X,Y,Z of real topology R >>which satisfy (1),(2),(3),(4). >>(without proof) >> >>(1) Y,Z is connected set >>(2) Y in W in Z , Y in X in Z > > I don't get this, how can a subset of R can be in a subset of R? > The elements of a subset of R are numbers, aren't subsets of R. > This is a problem of the imprecise use of the word in. > Sloppy and confusing. > A person might say the number 1 is in the interval [0, 2], > and the same person might say the subset [1,2] is in the > same interval. The OP should probably have used a different > set of words. > How weird. Does 'in' mean 'subset'? That doesn't make sense. original problem is find the subset W,X,Y,Z of real topology R which satisfy (1),(2),(3),(4). (without proof) (1) Y,Z is connected set (2) Y C W C Z , Y C X C Z (2) W is connected set (4) X is not connected set (symbol A C B = A is proper subset of B) um.....(0,1) C (0,2) ....is this wrong ?? thank you very much for your advice. === Subject: Re: topology 22 > original problem is > find the subset W,X,Y,Z of real topology R > which satisfy (1),(2),(3),(4). > (without proof) > (1) Y,Z is connected set > (2) Y C W C Z , Y C X C Z > (2) W is connected set > (4) X is not connected set > (symbol A C B = A is proper subset of B) > um.....(0,1) C (0,2) ....is this wrong ?? > thank you very much for your advice. And whats this real topology, do you mean euclidean topology on real numbers? It's quite easy.. since X contains a connected set then you can easily use the trick of X having two connected components. Example: Y=(0,1), X=(0,1) union {2} W=(0,2), Z=(0,3) Jose Capco === Subject: Re: topology 22 >>find the subset W,X,Y,Z of real topology R >>which satisfy (1),(2),(3),(4). >> >>(1) Y,Z is connected set >>(2) Y in W in Z , Y in X in Z > > I don't get this, how can a subset of R can be in a subset of R? > The elements of a subset of R are numbers, aren't subsets of R. > > This is a problem of the imprecise use of the word in. > Sloppy and confusing. > A person might say the number 1 is in the interval [0, 2], > and the same person might say the subset [1,2] is in the > same interval. The OP should probably have used a different > set of words. > > How weird. Does 'in' mean 'subset'? That doesn't make sense. > original problem is > find the subset W,X,Y,Z of real topology R > which satisfy (1),(2),(3),(4). > (1) Y,Z is connected set > (2) Y C W C Z , Y C X C Z > (2) W is connected set > (4) X is not connected set > (symbol A C B = A is proper subset of B) > um.....(0,1) C (0,2) ....is this wrong ?? Howver subset and proper subset symbols don't do well in ascii. A C E for example is a word. Some use < and <=, which is very context sensitive and when talking both subset and less than in same statement as for example a < b ==> (b,r) < (a,r) could be bothersome. TeX uses subseteq and subset However for ascii, subset and subsetneq would be clearer for indeed proper subset means subset and /=. I use subset and proper subset as need for proper subset is infrequent. 'in' as 'element of' is clear. For a sequence, (x_n)_n within S can be more elucidating and precise, for (x_n)_n isn't a subset of S but only it's values, and again (x_n)_n not in S for it's not a element of S. === Subject: Re: Skolem's Paradox and why is math the way it is? |I have a question about the universe of discourse, could you please expand |what you mean when you say that there are larger realms of discourse than set |theory? Well, partly I had in mind that there isn't just the one system of sets (the cumulative hierarchy). There are also the non-well-founded sets and the like. Restricting to just well-founded sets is a way of ensuring a certain kind of good behavior, but surely not absolutely necessary. Also although there are often ways of representing mathematical objects as sets, it's somewhat artificial to do so in many cases. Meanwhile, there are constructions in category theory that appear to make sense, but are too big to be sets as they stand. Keith Ramsay === Subject: Re: Skolem's Paradox and why is math the way it is? > |I have a question about the universe of discourse, could you please expand > |what you mean when you say that there are larger realms of discourse than set > |theory? > Well, partly I had in mind that there isn't just the one system of > sets (the cumulative hierarchy). There are also the non-well-founded > sets and the like. Restricting to just well-founded sets is a way of > ensuring a certain kind of good behavior, but surely not absolutely > necessary. > Also although there are often ways of representing mathematical objects > as sets, it's somewhat artificial to do so in many cases. > Meanwhile, there are constructions in category theory that appear to > make sense, but are too big to be sets as they stand. > Keith Ramsay That's an interesting point about the cumulative hierarchy and the non-well-founded sets. Where I equated the cumulative hierarchy with the projectively completed ring of integers in the theory of ubiquitous ordinals, then when I consider ubiquitous ordinals with no foundation their ordinal value would not in the naive construction differ from their order type in the simple case where A={A}. Thus they would all coincide with U, the universal set, as ordinals, or there would be a lot of sets outside of the cumulative hierarchy, the concept of which can be used to represent the integers as mechanistic sets. Category theory, with its objects and arrows, or functions, does not seem to be outside of the realm of discourse of set theory. Please provide an example or to ZF of any abstraction of primary objects if applicable. What's the point of a fundamental set theory if everything is not a set? People often use ZF with classes, if they don't then they have to stab out their figurative eyes every time they see the words collection of all sets, which regenerate painfully. Then, when they're using that, ZF with classes, say class of all classes and their eardrums explode. Skolem. As has been discussed in this and other recent threads, and rather continuously for a hundred eternally, it can be easily seen that room for improvement in foundations exists. There are a wide variety of logical theories, most using damningly self-reflexive non-logical axioms, that plainly admit the universal set and as well other non-well-founded sets. cumulative hierarchy as ubiquitous ordinals is that all of the infinite ordinals are non-well-founded. That seems a decent naive resolution. Then, you can easily assume the sets are well-founded or not, and if so then there are ubiquitous naturals, else ordinals. Infinity: too big. Ross F. === Subject: Re: Skolem's Paradox and why is math the way it is? |> I didn't say anything about standards of proof, but since you ask, we |> do of course have standards. They are just informal, not set by a fixed |> axiom system. | |But different axioms systems are different. For instance you can have |a non-well founded set theory, then you usually have collection |instead of repalcement, but in a normal set theory class a proof of |collection is required. It's a mistake, though, to assume that when people are using two different axiom systems, they are using them intending for the sentences of the language to have two different interpretations, one for each axiom system. Sometimes they are only adding more or less of the things that they believe to be true under one given interpretation. It's ordinarily impossible to capture one's knowledge of mathematics in a formal system. If one believes that the axioms are true, and that the deductive rules are sound, then one normally believes that they are also consistent, but a system strong enough to capture a person's knowledge of mathematics presumably is strong enough for Goedel's incompleteness theorem to apply. So they believe the formal system to be consistent, but it's impossible to prove in the system. Hence if I start working in ZFC+con(ZFC), it's fairly unlikely that I'm doing so intending for the sentences I'm working with to have a different meaning from what I intended when I was just working with ZFC. I merely added one more thing that I believe to be true to the axioms. Keith Ramsay === Subject: Re: Set Theory |> |> As a result, people usually think one of two things, either that |> |> the continuum problem is hard, or that it's not a problem |> |> to solve. Platonists think of the problem as hard. It's a theorem |> |> of ZFC that c=aleph_x for some ordinal x. A Platonist would |> |> (ordinarily at least) believe that, and think that we just don't know |> |> yet which ordinal x is, whether it's 1, 2, or something else. On |> |> the other hand, there are people who think that the question is |> |> somehow undefined, and that it's meaningless to ask which |> |> ordinal x really is. |> | |> |If the universe of discourse is the heirarchy of sets you mentioned on |> |another thread, then is x a specific ordinal, or is it still unkown? |> It's a specific ordinal, although we may not know whether it's 1, |> 2, 3, or something else. |> The only way for it to make sense to say that the universe of discourse |> is indeed the cumulative hierarchy is to agree to at least part of the |> Platonists' position on it. | |Can you elaborate, I'm don't even understand what you are saying. |Things like agree to at least PART seems vague to me. Indeed, I was being a bit vague. The point is that lots of the standard philosophical positions opposed to Platonism would not agree that it makes sense to say that (we have decided) the cumulative hierarchy is our domain of discourse. The cumulative hierarchy is the class of pure, well-founded sets. I think that's fine. But some people consider it just fictional. The reason for the vagueness is that there are positions differing both from the ones treating it as a complete fiction and Platonism. It would be possible for a constructivist, for example, to accept the cumulative hierarchy as a valid construction without buying into Platonism. | What do you |have to do to consider that universe of discourse? I find this kind of how question hard to answer, because I can't tell what sort of answer you're looking for. If we want to take the integers as our universe of discourse (for doing number theory, say), what do we have to do? In very mundane terms, we do what we did in elementary school-- learn to count, learn to do operations on them, perhaps learn mathematical induction if we're lucky, and so on. At that point, we know what the integers are, to the extent that is needed to take them to be our universe of discourse in a more formal way. For the cumulative hierarchy it's similar. We perhaps acquaint ourselves with hereditarily finite sets {{},{{{}}}} something like the way we got acquainted with integers. Then maybe we choose to suppose that the hereditarily finite sets can be regarded as a whole as a larger kind of set. We can define subsets of it, families of subsets, and so on. Eventually someone describes the notion of rank, and we ask how high in rank it makes sense to let sets go. The way you ask this kind of question makes me uneasy, because I keep getting the impression you are essentially expecting a kind of answer that's actually impossible, without being able to articulate exactly what kind of expectation you have, so that we can hold it up to the light and show just why it's impossible to satisfy. It relates to the boostrapping problem I mentioned months back. It's difficult to explain how it is possible to build a foundation for a subject without the foundation itself being arbitrary, or it's being built on top of a still more fundamental foundation (which then still needs to be explained). In the case of the integers, I feel confident that the foundation is quite okay, and that we know what the integers are even by just a very informal introduction to them. | To me it's very |confusing, like if you assume that fewer sets exist by having GCH, |then you get choice sets that don't exist in other versions, is that |because the sets that can lack a choice function are between the |cardinals omege, 2^ omega, 2^(2^omega), etc? I'm not surprised you find it confusing, since I find the statement of the question confusing! It seems to me that you're imagining a mathematician changing the assumptions he's using, and this somehow going hand-in-hand with assuming a different class of sets as the domain of discourse. These two ideas *might* go through the mathematician's mind together, but there's no obvious relationship. To me, GCH is just another one of those conjectures that's probably untrue, but whose consequences we could explore anyway. Is what you're asking about a scenario where someone is considering a model M of ZF not satisfying GCH, and then shifts to considering a submodel N that is a model of ZF+GCH? Keith Ramsay === Subject: A problem in convexity I'm stuck in this problem: Let S be an infinite subset of the d-dimensional Euclidian space and let u be a point in the interior of convex hull of S. Prove that one can choose 2d points v1,...,v2d in S such that u lies in the interior of convex hull of v1,...,v2d. Till now, I find a way to prove the case when d=2, but can't figure out how to prove general cases. Any comments are highly appreciated. === Subject: Re: A problem in convexity > I'm stuck in this problem: > Let S be an infinite subset of the d-dimensional Euclidian space and > let u be a > point in the interior of convex hull of S. Prove that one can choose > 2d points v1,...,v2d in S such that u lies in the interior of convex > hull of v1,...,v2d. It is clear to me that d + 1 points are enough, since u is in the interior of a d-simplex that lies in the interior of the convex hull of S. Or I misunderstood the question. Takao === Subject: Re: A problem in convexity 3QLpj-NoP*NzsIC,boYU]bQ]H'y<#4ga3$21: > I'm stuck in this problem: > Let S be an infinite subset of the d-dimensional Euclidian space and > let u be a > point in the interior of convex hull of S. Prove that one can choose > 2d points v1,...,v2d in S such that u lies in the interior of convex > hull of v1,...,v2d. > It is clear to me that d + 1 points are enough, since u is in the > interior of a d-simplex that lies in the interior of the convex hull of > S. Or I misunderstood the question. If the points all lie along the coordinate axes and u is the origin then at least 2d points are necessary. Key word is interior. This is known as Steinitz' theorem but that name also refers to the one about characterizing skeletons of 3d polyhedra and the one about the existence of algebraic closure of fields. If the word interior were omitted then it would be Caratheodory's theorem and d+1 would suffice. E. Steinitz. Bedingt Konvergente Reihen und Konvexe Systeme I. J. reine angew. Math., 143:128-175, 1913; II. J. reine angew. Math., 144:1-40, 1914; III. J. reine angew. Math., 146:1-52, 1916. -- David Eppstein Computer Science Dept., Univ. of California, Irvine http://www.ics.uci.edu/~eppstein/ === Subject: Re: A problem in convexity > Let S be an infinite subset of the d-dimensional Euclidian space and > let u be a > point in the interior of convex hull of S. Prove that one can choose > 2d points v1,...,v2d in S such that u lies in the interior of convex > hull of v1,...,v2d. > Till now, I find a way to prove the case when d=2, but can't figure > out how to prove general cases. How did you get this problem? This problem is exciting. The following is my solution. Many details are skipped or compressed, because the solution is long. = = = = Notations & Definitions = = = = Let d be a natural number. (d = 1,2,3, ...) R^d is the d-dim Euclidian space. If S is a subset of R^d, we say ch(S) = the convex hull of S, int(S) = the interior of S, |S| = the cardinality of S, A /= B iff A is a subset of B. U is always the set-union symbol, in this posting. For example, U_{n in Z} (n, n+1) = R Z. B(p;r) is the d-dim closed ball with center p and of radius r > 0. If p is a nonzero point in R^d, L(p) = { r p: r > 0 }. If p_1, p_2, .. p_n are points in R^d, and L is a linear m-dim subspace of R^d, q is a point in R^d, and q+L contains the points p_1, ..., p_n, and m is the minimal dimension possible such, then we say, q+L is a plane generated by p_1, ..., p_n. (Note that a plane is a subspace iff it contains 0.) (Note that, in this definition, planes need NOT be 2-dim.) If p_1, p_2, ..., p_n are points in R^d, and if a_1, a_2, ..., a_n are nonnegative real numbers whose sum is 1, and if a point q satisfies q = a_1 p_1 + a_2 p_2 + ... + a_n p_n, then we say q is a 1-combination of p_1, p_2, ..., p_n . = = = = Lemma 1 = = = = [ Lemma 0 ] If S is a subset of R^d, then ch(S) = {all the 1-combinations of finitely many points of S }. [ how to prove this ] 1. Show that the set on the right side is convex. 2. Show that every point in the set is in ch(S). 3. Then conclude the equality. // [ Lemma 1/2 ] Suppose P is a finite subset of R^d. If q is a 1-combination of the points in P, then q is a 1-combination of d+1 or fewer points in P. [ how to prove this ] Suppose p_1, p_2, ..., p_n are a smallest number of points in P such that q is a 1-combination of p_1, ..., p_n. And suppose n > d+1, then derive a contradiction using the minimality of n. Then conclude n <= d+1. // [ Lemma 1 ] If S be a subset of R^d, then ch(S) = U_{P/=S, |P|<=d+1} ch(P) [ how to prove this ] Use Lemma 0 and Lemma 1/2. // [ Lemma 2 ] Suppose O is a subset of R^d with nonempty interior. Suppose {C_h : h in H} is a collection of convex subsets of R^d such that O /= C_h for each h in H. (H can be any set) If C_oo = U_{h in H} C_h, then int(C_oo) = U_{h in H} int(C_h). [ proof ] U_{h in H} int(C_h) /= int( C_oo ) is obvious. So, let's show int(C_oo) /= U_{h in H} int(C_h). There are u in R^d and s > 0, such that B(u;s) /= O. Let u+v be an arbitrary point in int(C_oo). Then for some t > 0, B(u+v;t) /= C_oo For some r > 0, w = u+(1+r)v is in B(u+v;t), and so is in C_oo, So w is in C_h' for some h' in H. Since B(u;s) U {w} /= C_h', and since u+v is in int(ch( B(u;s) U {w} )), u+v is in int(C_h'). // = = = = a Theorem = = = = [ a Theorem ] Suppose S is a subset of R^d such that 0 is in int(ch(S)). Then there is a subset T of S such that 0 is in int(ch(T)), |T|<=2d. [ summary of proof ] Two cases. Case 1: S is finite. In this case, suppose d>1, for the case d=1 is trivial. There is nonzero u in R^d, such that every (d-2)-dim plane generated by points of S does not intersect L(+u) U L(-u). Let D be the boundary of ch(S). D is a (d-1)-dim surface surrounding the point 0. L(+u) meets D at a point v_1. There is a (d-1)-dim plane P_1 such that v_1 is in P_1 and ch(S) is entirely contained in one of the two regions cut out of R^d by P_1. (Informaly, P_1 is a plane tangent to ch(S) at v_1. this P_1 may not be unique.) Let E be the intersection of P_1 and S. Now, think of P_1 as another (d-1)-dim Euclidean space, E is inside that Euclidean space, and v_1 is in ch(E), so by applying Lemma 1 to E as inside P_1, it follows that there is subset T_1 of E such that v_1 is in ch(T_1) and |T_1|<=(d-1)+1=d. Because of how we have chosen u, v_1 is not in the (P_1)-boundary of ch(T_1). Therefore v_1 is in the (P_1)-interior of ch(T_1). Same arguments for L(-u) gives v_2, P_2, T_2 and v_2 is in P_2-interior of ch(T_2). Therefore, 0, which is in ch{v_1, v_2}, is in interior of ch(T_1 U T_2). And |T_1 U T_2| <= d+d = 2d. So we have constructed T = T_1 U T_2, as desired. Case 2: S is infinite. Let {D_h : h in H} be the collection of all the sets of d+1 or fewer points in S. Then, by Lemma 1, U_{h in H} ch(D_h) = ch(S). Let P be a maximum-dim plane generated by finitely many points in S. Then P is generated by some finitely many points q_1,q_2, ...,q_n in S. This P, by the maximality of the dim(P), must contain every point of S. So, S /= P, and hence, ch(S) /= P. But since S has nonempty interior, so does P. Since every proper plane of R^d has empty interior, P = R^d. So, q_1,q_2, ...,q_n generates R^d. Therefore ch {q_1, ..., q_n} has nonempty interior. Let E_h = {q_1, ..., q_n} U D_h ,for each h. Then U_{h in H} ch(E_h) = S. ch{q_1, ... , q_n} /= ch(E_h) for each h. So by applying Lemma 2 to {ch(E_h) | h in H}, we see U_{h in H} int(ch(E_h)) = int(ch(S)). So, 0 is in int(ch(E_h')) for some h' . Furthermore, E_h' is finite. so we are now in Case 1 about E_h' . // [ a equivalent form of the theorem ] Suppose S is a subset of R^d such that 0 is in int(ch(S)), |S|>=2d. then one can choose 2d distinct points p_1, ... p_2d such that 0 is in int(ch({p_1, ... p_2d})) . // I hope a simple proof is somewhere. - - - Dae-jung Yoo (IGNJSA YOO) (Delete DELETE to reply by e-mail) === Subject: Re: A problem in convexity >> Let S be an infinite subset of the d-dimensional Euclidian space and >> let u be a >> point in the interior of convex hull of S. Prove that one can choose >> 2d points v1,...,v2d in S such that u lies in the interior of convex >> hull of v1,...,v2d. >> Till now, I find a way to prove the case when d=2, but can't figure >> out how to prove general cases. >How did you get this problem? This problem is exciting. >The following is my solution. Many details are skipped or >compressed, because the solution is long. ... >I hope a simple proof is somewhere. See Caratheodory's theorem. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada === Subject: Definition of Entire Function type=text/plain; boundary=----=_NextPart_000_4439_01C4DB29.433F23D0 This is a multi-part message in MIME format. ------=_NextPart_000_4439_01C4DB29.433F23D0 Taken from MathWorld: If a complex function is analytic at all finite points of the complex plane , then it is said to be entire Since there are many reasonable 1-1 onto mappings of the Complex Plane to itself that map the point at infinity to a finite point (e.g. 1/z), is it just historical that the definition singles out the point at infinity and doesn't instead say If a complex function is analytic except for one singularity, then it is 'entire'? Norm ------=_NextPart_000_4439_01C4DB29.433F23D0 name=eimg1183.gif Content-Location: http://mathworld.wolfram.com/eimg1183.gif