Compression theory reference?

[John Denker]

I wrote:
>>
>>  4) Don't forget the _recursion_ argument.  Take their favorite
>> algorithm (call it XX).  If their claims are correct, XX should
>> be able to compress _anything_.   That is, the output of XX
>> should _always_ be at least one bit shorter than the input.
>> Then the compound operation XX(XX(...)) should produce something
>> two bits shorter than the original input.  If you start with a
>> N-bit message and apply the XX function N-1 times, you should be
>> able to compress each and every message down to a single bit.

Matt Crawford wrote:
> 
> Plus a string of log(N) bits telling you how many times to apply the 
> decompression function!
> Uh-oh, now goes over the judge's head ...

Actually you don't need to adjoin log(N) bits.  But perhaps my
assertion would benefit from some clarification.

I emphasize that I am only discussing messages of length N,
where N is some pre-chosen number.  For concreteness, let's
choose N=10.

I repeat my assertion that _if_ XX can compress any string,
shortening it by one bit, and _if_ you know that the original
messages each have exactly 10 bits, _then_ any 10-bit message
can be compressed down to a single bit.

I have proved that XX is ridiculous in this one case.

My function YY := XX^9 is less general than XX.  XX works
on any input, whereas YY by its definition only applies to
10-bit messages.

The fact remains that we have a proof by contradiction.  We
assume by way of hypothesis that the bad-guys are right, namely
that XX exists and has the properties they assign to it.  Then
I can construct YY.  But YY is ridiculous, through no fault of
mine.  Ergo the bad guys are wrong, i.e. no such XX can exist.

With a little more work I could construct a more powerful and/or
more general version of YY ... but that would be doing more work
than is required.  Their XX stuck its neck out;  it is not
required for my YY to stick its neck out in the same way.  The
requirement, as I understood it, was to prove the bad guys
wrong.  Well, the bad guys have been proved wrong.  If something
more is required, please explain the requirements in more detail.

   (BTW I suppose it would be better to call this the 'iterated
   composition' argument rather than the recursion argument.)

Hadmut wrote:

> I found some outside Germany. But they didn't give me a paper with 
> signature, just e-mails. Will see whether the court will accept that. 

Ask your legal advisor.

In the US, getting such emails admitted as evidence would be
problematic.  Each jurisdiction (I assume) has its own standards
for how affidavits should be prepared.  Figure out the rules,
and play by the rules.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com