Re: An Interesting Problem

From: Peter Webb (webbfamily-diespamdie_at_optusnet.com.au)
Date: 03/27/05 

Date: Sun, 27 Mar 2005 11:28:38 +1000

"Absque Erus" <pirxthepilot@canoemail.com> wrote in message
news:1111885088.595938.120790@f14g2000cwb.googlegroups.com...
> Hello all,
>
> Due to recent spreading of some diseased laws to my country, brought
> (bought?) to us by a certain group of wealthy individuals whose
> monetary concern is to control all mechanisms of distribution of
> information, I am investigating a method of defeating their schemes in
> a final, absolute and irrevocable way ... OK, stop laughing, and read
> on.
>
> The method involves creation of a system whereby the data being traded
> between participants does NOT contain any sequences of integers which
> are "property" of the greed-mongers in question, and furthermore, the
> data exchanged cannot be plausibly claimed to be "derived" from the
> said "property". Or more precisely, any such claim can be easily and
> spectacularly demonstrated to be absurd. And yet the system will allow
> for basically any arbitrary data to appear by magic of science just
> where it is needed without being explicitly transmitted. Furthermore,
> any attempts to outlaw the transmission of the data that is being
> transmitted, will result in a ban on all mathematical functions in
> domain of integer numbers (which I hope will prove impossible for even
> the most moneyed interests).
>
> Additionally, a secondary objective (which I shall call "The Adding
> Insult To Injury Feature") is that the proposed system should be MORE
> data bandwidth efficient then the existing so-called P2P systems.
>
> Unfortunately, while my understanding of technologies involved is
> rather deep, my grasp of computational mathematics is not sufficient to
> avoid likely reinventing of the wheel (poorly) on my behalf.
>
> Thus I decided to ask the dwellers of this group whom I guess to be
> experts in the area.
>
> The problem is defined in mathematical terms as follows:
>
> Given two (or more) pairs of arbitrary sequences Sc1,Sf1 and Sf2,Sf3 of
> integer numbers in range 0-255, what is the least computationally
> expensive function f such that Sc1=f(Sf1) and Sf2=f(Sf3)? In other
> words I am seeking an algorithm for designing the least computationally
> expensive (or close to it) function Y=f(X) where X and Y are domains of
> (very large) integer numbers for which I have two (or more)
> pre-determined known data points.
>
> Additional considerations are: the sequences will in practice be of
> significant length and the method of deriving the function f should
> ideally also be not excessively computationally expensive.
>
> Please forgive me if this turns out to be a trivial exercise, after all
> I am not a mathematician.
>
> On the other hand should the problem prove interesting, I will on
> request provide further details of the scheme and any clarifications as
> needed.
>
> Naturally, this method will be used in freely available (GPL) software
> and I will duly and prominently display any notices of authorship of
> the algorithm(s) if asked to.
>
> AE
>

If I understand your problem correctly, there is no reasonable solution of
the sort you want.

Let me give an example of what I think you want. You have two sequences

a(n) 12, 2, 7, 32, 5 ...
b(n) 9, 23, 1, 16, 4 ....

You want a function f(a(n)) = b(n)

Well, assuming that none of the a(n) values repeat, here is a function that
does what you want ...

Define f(12) =9, f(2)=23, f(7)=1, f(32)=16, f(5) = 4 ......

This is a mathematical function, and one which is easy to compute.

However, I suspect that you want something mare natural looking, with
exponentials and products of terms and stuff like that.

Well, you could invent a function that looks like

f(x) = x(x-1)(x-2)(x-3)...(x-11)(x-13)(x-14) ...(x-32)*9 / (12*11*10
....*-20)

Note that (x-12) is missing from the product.

If x=12, then f(x)=9, otherwise the value is 0, because an least one of the
x- terms is zero.

So thise gives you an equation where f(x)=0 except f(12)=9.

Make the same sort of eqn for g(x)=0 except at g(2)=23

Keep making these equations for every term, add them togerther, you end up
with a polynomial of degree n (where n is the number of terms in the two
sequences) that maps a(n) to b(n).

But what's the point? You just end with an arbitrary looking equation with n
terms. Any scheme for mapping one random sequence to another will result in
something with n arbitrary numbers. Computationally you are better off just
listing the values the function takes as I did above:

Define f(12) =9, f(2)=23, f(7)=1, f(32)=16, f(5) = 4 ......

Turning it into complicated mathemeitical expression (eg a polynomial) does
not make it any more of a function, doesn't reduce the data storage
required, and doesn't seem to add anything in of itself (although there may
be security advantages, but you haven't asked about these).

Relevant Pages

  • An Interesting Problem
    ... I am investigating a method of defeating their schemes in ... any attempts to outlaw the transmission of the data that is being ... my grasp of computational mathematics is not sufficient to ... the sequences will in practice be of ...
    (sci.math)
  • Re: Largest provable BB(N)?
    ... |correct to argue that induction only involves the numbers ... That is, the induction principle assumes ... sequences of tally marks were used to ... |view of mathematics, the subject matter of mathematics is ...
    (sci.math)
  • RE: Article: Model Selection and the Molecular Clock
    ... The words supply meaning. ... mathematics must work with and not against, ... of gene and genome sequences. ... evolutionary genetics" to PRECEDE "the data to which they are applied" only ...
    (sci.bio.evolution)
  • Re: Math education myth question
    ... this is wildly incorrect as to fact. ... Now there's another fellow called Thompson, ... divided up human progress in mathematics as follows: ... `Thompson Scheme': ...
    (talk.origins)
  • Re: Universal grammar
    ... applying it to patterns defined as "sets of token sequences". ... You seem to see it as a paradox of encapsulated infinity, ... My logical gloss of the proof is that "within a pattern saying one ... mathematics to prove either way whether all distributions can be ...
    (sci.lang)