Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Improve counting of local solutions for QuadraticForm at p=2 #38679

Closed
1 task done
WvanWoerden opened this issue Sep 19, 2024 · 2 comments · Fixed by #38680
Closed
1 task done

Improve counting of local solutions for QuadraticForm at p=2 #38679

WvanWoerden opened this issue Sep 19, 2024 · 2 comments · Fixed by #38680
Labels
t: enhancement

Comments

@WvanWoerden
Copy link
Contributor

Problem Description

Given a QuadraticForm Q it is currently infeasible to compute Q.siegel_product(m) when Q.dim() >= 8.
The reason for this is that Q.local_density(p,m) for p=2 needs to compute local (good) solutions modulo 8 which is done with a naive brute-force approach by count_congruence_solutions__good_type(2, 3, m, ..., ...).

Proposed Solution

The solutions mod 8 can be computed efficiently by:

  1. put Q in local normal form (which is already done),
  2. count all solutions Q_block[v] = k mod 8 per Jordan block for each k=0,...7 (this can be done naively)
  3. compute the convolution of the solutions of all blocks
  4. return the count at m

Of course this could be implemented in a general way and not just for p=2 or modulo 8.

Alternatives Considered

None.

Additional Information

I will propose a pull request with the feature soon.

Is there an existing issue for this?

  • I have searched the existing issues for a bug report that matches the one I want to file, without success.
@WvanWoerden WvanWoerden mentioned this issue Sep 19, 2024
Merged
5 tasks
vbraun pushed a commit to vbraun/sage that referenced this issue Oct 18, 2024
sagemathgh-38680: Improve counting of local solutions for QuadraticFo…
0b24538 
…rm at p=2

    
Fixes sagemath#38679.

Introduces new method `CountAllLocalGoodTypesNormalForm(Q, p, k, m,
zvec, nzvec)` to compute the number of local solutions of 'good type'
for Q[v] = m mod p^k when Q is in local normal form at p.
This replaces the use of the slow brute-force function
`CountAllLocalTypesNaive` indirectly used in
`local_good_density_congruence_even` for (p,k)=(2,3) .

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [ ] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies
    
URL: sagemath#38680
Reported by: WvanWoerden
Reviewer(s): Frédéric Chapoton, Sebastian A. Spindler
vbraun pushed a commit to vbraun/sage that referenced this issue Oct 20, 2024
sagemathgh-38680: Improve counting of local solutions for QuadraticFo…
521037d 
…rm at p=2

    
Fixes sagemath#38679.

Introduces new method `CountAllLocalGoodTypesNormalForm(Q, p, k, m,
zvec, nzvec)` to compute the number of local solutions of 'good type'
for Q[v] = m mod p^k when Q is in local normal form at p.
This replaces the use of the slow brute-force function
`CountAllLocalTypesNaive` indirectly used in
`local_good_density_congruence_even` for (p,k)=(2,3) .

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [ ] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies
    
URL: sagemath#38680
Reported by: WvanWoerden
Reviewer(s): Frédéric Chapoton, Sebastian A. Spindler
vbraun pushed a commit to vbraun/sage that referenced this issue Oct 23, 2024
sagemathgh-38680: Improve counting of local solutions for QuadraticFo…
59a2bdc 
…rm at p=2

    
Fixes sagemath#38679.

Introduces new method `CountAllLocalGoodTypesNormalForm(Q, p, k, m,
zvec, nzvec)` to compute the number of local solutions of 'good type'
for Q[v] = m mod p^k when Q is in local normal form at p.
This replaces the use of the slow brute-force function
`CountAllLocalTypesNaive` indirectly used in
`local_good_density_congruence_even` for (p,k)=(2,3) .

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [ ] The description explains in detail what this PR is about.
- [x] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies
    
URL: sagemath#38680
Reported by: WvanWoerden
Reviewer(s): Frédéric Chapoton, Sebastian A. Spindler
@vbraun vbraun closed this as completed in 5c90b60 Oct 26, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
t: enhancement
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Improve counting of local solutions for QuadraticForm at p=2 WvanWoerden/sage
3 participants
@WvanWoerden and others