On Oct 25, 2007, at 4:23 PM, Martin Albrecht wrote: > On Friday 26 October 2007, Robert Bradshaw wrote: >> This is an interesting construction, but I am wondering if a uniform >> distribution for all polynomials of specified degree < d, with a >> specified number of terms, is the most natural one to give, and how >> grave the impact is on efficiency. (Depending on the coefficient >> ring, this goal may not even be achievable). > > Yes, a random boolean multivariate polynomial will have $MM/2 > monomials i.e. > 1/2 of all possible monomials. That is okay, we are not enforcing > #T to be > achieved but we are enforcing that the coefficients determine if we > get to #T > or not rather than the implementation.
For boolean multivariate polynomials, it makes sense to talk about the number of terms of a random polynomial of a given degree, because you are working with a finite space, but this has a very different feel than a random polynomial over an infinite ring, say, Z. > Actually, Steffen jokingly proposed earlier to have .some_element() > besides .random_element() which gives you a somewhat random element > whereas .random_element() actually gives you something very random. The random_element() function should probably take arguments specifying the distribution--some_element makes it sound like it's always going to give the same thing. >> Also, rather than specifying maximum degree/number of terms, it might >> make more sense (and be much after to implement) to use a >> distribution with an expected degree and/or number of terms. > > can you elaborate on this, I don't really understand that point. My point is that just because one isn't using a uniform distribution doesn't mean that the polynomials produced are any less random. For instance, fix a degree d and a (real) distribution X with support [0,infinity) and expected value 1. Now let r_1, ..., r_n be chosen out of X and let f = sum x_i ^ round(d/n * r_i) Now f is a monomial with expected (i.e. average) degree d (I think-- not sure how bad the discontinuous rounding would mess things up), though it may have degree more or less than d, and though it is not uniformly chosen from any set is not any less "random." It can also be computed very quickly. - Robert --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
