Modular Subset "Product" Problem
 

Is there info on how to solve this type of problem somewhere?

Suppose you have a set of congruences A[i] mod B[i] such that A[i] is a random integer and B[i] is a random prime. (the primes are not repeated)
Now merge one congruence A[i] mod B[i] with another congruence and join the resulting congruence with other unjoined congruences as many times as needed until you get a congruence with the lowest ratio of A/B that is possible from the set of congruences.

[QUOTE=vector;127870]Is there info on how to solve this type of problem somewhere?

Suppose you have a set of congruences A[i] mod B[i] such that A[i] is a random integer and B[i] is a random prime. (the primes are not repeated)
Now merge one congruence A[i] mod B[i] with another congruence and join the resulting congruence with other unjoined congruences as many times as needed until you get a congruence with the lowest ratio of A/B that is possible from the set of congruences.[/QUOTE]

This is pseudo-babble; It is not a math problem. It is non-rigorous
GIBBERISH.

You have failed to specify the meaning of "merge one congruence with
another". Does "unjoined" mean the same as "not yet merged"? One
presumes so, but the word "join" is also undefined. Just because
"join" and "merge" are synonyms in English does not guaranteee that
they must mean the same thing in a math problem.

And you have not defined A or B. You have defined A[i]
and B[i], but the meanings of A, B, and A/B are vague mysteries.

And finally, there is no such thing as a "random integer" or "random prime".
They don't exist.

Joining/merging means using the Chinese remainder theorem on congruences (a1 mod b1) and (a2 mod b2) to get another congruence of the form (a3 mod b1*b2).

For a congruence (A mod B) or (3 mod 11) the ratio A/B is 3/11 or 0.272727272727272727.....

The set of congruences can be: (2 mod 3);(3 mod 5);(4 mod 7);(1 mod 11)

The Chinese remainder theorem can be used on more than two congruences at the same time.
This problem involves using Chinese remainder theorem on a specific subset of these congruences to produce a congruence A mod B such that the ratio A/B is smaller than the ratio produced by using the Chinese remainder theorem on any other subset of congruence set.

I have no comment for your disbelief in random numbers. :crank:

I remember a report once stating that 17 is the least random number.

Ask people to think of a random number and 17 is given more often than any other number.

I thought it was 37

OK. And what is the smallest uninteresting number?

well, 43 obviously

which makes it very uninteresting indeed

Reminds me of a code snipped I've seen somewhere:
[CODE]

/* Returns a random integer */
int random()
{
return 4; /* Chosen by fair dice roll */
}
[/CODE]

[QUOTE=vector;127885]Joining/merging means using the Chinese remainder theorem on congruences (a1 mod b1) and (a2 mod b2) to get another congruence of the form (a3 mod b1*b2).

For a congruence (A mod B) or (3 mod 11) the ratio A/B is 3/11 or 0.272727272727272727.....

The set of congruences can be: (2 mod 3);(3 mod 5);(4 mod 7);(1 mod 11)

The Chinese remainder theorem can be used on more than two congruences at the same time.
This problem involves using Chinese remainder theorem on a specific subset of these congruences to produce a congruence A mod B such that the ratio A/B is smaller than the ratio produced by using the Chinese remainder theorem on any other subset of congruence set.

I have no comment for your disbelief in random numbers. :crank:[/QUOTE]

You are clueless. Nothing in my post indicated that I "disbelieve" in random
numbers. I said that random integers and random primes do not exist.
They do not. Random integers DRAWN FROM A SUBSET OF Z with a specified density function exist.

There is no way to draw an integer at random from the set of all integers.
There is no way to draw a prime at random from the set of all primes.
You must specify a density function.

Although I do not have the details, I am sure that your problem is NP-Complete. I have a tentative sketch, based on taking logarithms after
combining two of your congruences that reduces your problem to a
subset-sum problem.

[QUOTE=R.D. Silverman;127916]You are clueless. Nothing in my post indicated that I "disbelieve" in random
numbers. I said that random integers and random primes do not exist.
They do not. Random integers DRAWN FROM A SUBSET OF Z with a specified density function exist.[/QUOTE]Warning: nitpicking follows.

My density function is that the probability of drawing x from Z is 1/N if 1<=x<=N and 0 otherwise. :wink:


Paul

[quote=R.D. Silverman;127916]
Although I do not have the details, I am sure that your problem is NP-Complete. I have a tentative sketch, based on taking logarithms after
combining two of your congruences that reduces your problem to a
subset-sum problem.[/quote]

Why are you taking logarithms of the congruences? This will not accomplish anything. You cant represent and apply the Chinese remainder theorem operation logarithmically, your algorithm would just return utter nonsense.

If this problem involved multiplying a bunch of numbers together then it might work. I called this a product problem because multiplication is the closes analogy I know to operation of Chinese remainder theorem.

The best algorithm I have so far involves finding "common remainders of remainders." For example: (9 mod 33) and (2 mod 7) makes (9 mod 231) because (9 mod 7) = (2 mod 7)
Now if there was a way to use Chinese remainder theorem on a "small congruence" and a "large congruence which has a small remainder" such that the "large congruence's remainder increases but not by too much" this algorithm be usable in practice because the first algorithm would be able to be reused efficiently.

[QUOTE=vector;128060]Why are you taking logarithms of the congruences? This will not accomplish anything. You cant represent and apply the Chinese remainder theorem operation logarithmically, your algorithm would just return utter nonsense.

If this problem involved multiplying a bunch of numbers together then it might work. I called this a product problem because multiplication is the closes analogy I know to operation of Chinese remainder theorem.

The best algorithm I have so far involves finding "common remainders of remainders." For example: (9 mod 33) and (2 mod 7) makes (9 mod 231) because (9 mod 7) = (2 mod 7)
Now if there was a way to use Chinese remainder theorem on a "small congruence" and a "large congruence which has a small remainder" such that the "large congruence's remainder increases but not by too much" this algorithm be usable in practice because the first algorithm would be able to be reused efficiently.[/QUOTE]

You are truly retarded. You need to learn to read. Taking logarithms
***AFTER*** combining the congruences turns a multiplicative problem
into an additive one. Instead of minimizing A/B, you minimize log(A) -
log(B). This transforms the problem into one that is similar to the subset
sum problem.

Your "problem" (and it is bizarre) is an NP-Complete combinatorial
search problem.

I know far more than you do about BOTH number theory and
combinatorial optimization.

[QUOTE=vector;127870]Suppose you have a set of congruences A[i] mod B[i] such that A[i] is a random integer and B[i] is a random prime. (the primes are not repeated)
Now merge one congruence A[i] mod B[i] with another congruence and join the resulting congruence with other unjoined congruences as many times as needed until you get a congruence with the lowest ratio of A/B that is possible from the set of congruences.[/QUOTE]

I think your problem can be posed as a variation of "noisy CRT decoding" and thus solved using methods based on lattice reduction. In particular, Theorem 2.1 (page 4) from Dan Boneh's paper: [url]http://citeseer.ist.psu.edu/boneh00finding.html[/url] seems to be applicable.

Your target is slightly different from the CRT decoding since you're interested in minimizing the ratio m/amp(m) but Theorem 2.1 gives a way to make it at most B/P^epsilon. I think for an appropriate choice of parameters it will deliver you a solution (or at least good approximation to it).

[QUOTE=R.D. Silverman;128075]You are truly retarded. You need to learn to read. Taking logarithms
***AFTER*** combining the congruences turns a multiplicative problem
into an additive one. Instead of minimizing A/B, you minimize log(A) -
log(B). This transforms the problem into one that is similar to the subset
sum problem.[/QUOTE]
If people do not understand what you are saying, that does not mean they are retarded. Perhaps, you are lacking an ability to explain things. And being rude to people does not help them to understand better.

btw, there seems to be no direct connection to the subset-sum problem here. The closest thing I can see is minimization of an expression like frac(C / P) over P, where C is a constant positive integer (that can be as large as the product of all moduli), P is the product of some moduli (of our choice), and frac() is a fractional part of the number. Bringing an additional integer variable N (that will stand for an integer part of C/P) leads to minimization of C / P - N, keeping it non-negative. Anyway, because of this extra "N", taking logarithms won't lead to a subset-sum problem, in particular, since both P and N can be about sqrt(C) and there is no obvious way to "linearize" log( C / P - N ).

[QUOTE=Kees;127907]well, 43 obviously

which makes it very uninteresting indeed[/QUOTE]

That's interesting because the largest anti interesting number is 43^2
(all other anti interesting numbers are negative)

Since this question deals with subset sums I might as well as this here...

Is it easier to solve subset sum problems whose sets can be partitioned into two, similarly sized, super increasing sets.

So a problem with : {2,3,5,7,11,17,25,38,58,86,129,194,292}
can be partitioned into: {2,5,11,25,58,129,292} and {3,7,17,38,86,194}