Opened 9 years ago

Closed 2 years ago

#11850 closed enhancement (wontfix)

random element of ideal

Reported by: dangtuanhiep Owned by: malb
Priority: trivial Milestone: sage-duplicate/invalid/wontfix
Component: commutative algebra Keywords: random, ideal, sd34
Cc: ranosch, burcin, tscrim, jakobkroeker Merged in:
Authors: Hiep Dang, Burcin Erocal Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

return a random element of given ideal.

Attachments (2)

ideal_random_element.patch (2.2 KB) - added by dangtuanhiep 9 years ago.
random_element.patch (2.7 KB) - added by dangtuanhiep 9 years ago.

Download all attachments as: .zip

Change History (21)

Changed 9 years ago by dangtuanhiep

comment:1 Changed 9 years ago by dangtuanhiep

  • Authors set to Hiep Dang

comment:2 Changed 9 years ago by ranosch

  • Cc ranosch added

comment:3 Changed 9 years ago by dangtuanhiep

  • Status changed from new to needs_review

comment:4 Changed 9 years ago by dangtuanhiep

  • Cc burcin added

comment:5 Changed 9 years ago by ranosch

  • Keywords sd34 added

comment:6 Changed 9 years ago by malb

  • Status changed from needs_review to needs_work

I don't think this code

sum(g * self.ring().random_element(degree - g.degree(), *args, **kwds) for g in self.gens()) 

returns a uniformly random element up to the given degree.

  • one should at least use the Gröbner basis instead of gens()
  • even then I don't think this code returns uniformly random elements up to some degree, because of potential cancellations.

I suggest to do:

f = P.random_element()
f = f - f.reduce(self)

which is "as random" as P.random_element() because P = I \oplus P/I.

In case you are wondering: sampling uniform from an ideal given a set of generators is as hard as computing the GB (at least for dense/zero-dimensional systems): http://eprint.iacr.org/2011/289

Changed 9 years ago by dangtuanhiep

comment:7 Changed 9 years ago by dangtuanhiep

  • Authors changed from Hiep Dang to Hiep Dang, Burcin Erocal

comment:8 Changed 8 years ago by dangtuanhiep

Hi Burcin,

I am trying to apply this patch to version 5.0, but I get this error

Error compiling Cython file:


...

elif terms == 0:

return self._zero_element

if degree == 0:

if terms != 1:

raise TypeError?, "Cannot compute polynomial with more terms than exist."

return k.random_element(kwargs)


sage/rings/polynomial/multi_polynomial_ring_generic.pyx:760:20: local variable 'k' referenced before assignment Error running command, failed with status 256. Error installing modified sage library code.

comment:9 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:13 Changed 4 years ago by jmantysalo

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to needs_review

I think that this has been done, as multi_polynomial_ideal.py now has random_element().

comment:14 Changed 4 years ago by jmantysalo

  • Cc tscrim added

Travis, can you confirm this wontfix/duplicate?

comment:15 Changed 4 years ago by jakobkroeker

  • Cc jakobkroeker added

comment:16 Changed 3 years ago by jmantysalo

Just pingin, can we close this?

comment:17 Changed 2 years ago by roed

  • Status changed from needs_review to positive_review

Sounds good to me.

comment:18 Changed 2 years ago by jmantysalo

Even wontfix-tickets need the reviewer's name. I think that otherwise this won't be semiautomatically closed.

comment:19 Changed 2 years ago by embray

  • Resolution set to wontfix
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.